We report evidence for the first generation of XUV spectra from relativistic surface high-harmonic generation (SHHG) on plasma mirrors at a kilohertz repetition rate, emitted simultaneously and correlated to the emission of energetic electrons. We present measurements of SHHG spectra and electron angular distributions as a function of the experimentally controlled plasma density gradient scale length $L_mathrm{g}$ for three increasingly short and intense driving pulses: 24~fs (9 optical cycles) and $a_0=1.1$, 9~fs (3.5 optical cycles) and $a_0=1.8$, and finally 4~fs (1.7 optical cycles) and $a_0approx2.0$. For all driver pulses, we observe relativistic SHHG in the range $L_mathrm{g}in[lambda/25,lambda/10]$, with an optimum gradient scale length of $L_mathrm{g}approxlambda/15$.