How does a shift in time domain result in phase shift in frequency spectrum?
Consider first that in the time domain that a phase rotation or shift in phase or phase shift specifically is done by multiplying the waveform with $e^{j\phi}$ which rotates or shifts the complex phase for each sample in time by $\phi$. Realize that $e^{j\phi}$ is a complex phasor of magnitude $1$ and angle $\phi$. In contrast a time delay is given as $x(t-t_o)$ as the OP has indicated.

This is no different in the frequency domain where we have a complex waveform just the same but with a different independent variable (frequency instead of time). Similarly we can multiply the frequency domain waveform by the $e^{jt_o \omega}$ which for a given sample at frequency $\omega$ will cause a constant phase rotation of that sample.

In the frequency domain $e^{jt_o \omega} = cos(t_o \omega) + jsin(t_o \omega)$ is a constant phase shift of $t_o \omega$ for each sample given by $\omega$ and is not a scaling of frequency as the OP suspects since we are in the frequency domain (in the time domain a scaling of frequency would be of similar form given as $y(t) = cos((\omega t_o) t)$ but that is not what is occuring here since we have $Y(j\omega) = X(j\omega)e^{-j\omega t_o}$. 

Consider a very simple case of $X(j\omega_1) = Ae^{j\phi_1}$, which means that the magnitude of frequency $\omega_1$ is $A$ and the phase of this frequency is $\phi_1$.  After the time delay given by $x(t-t_o)$ the result would be:

$$Ae^{j\phi_1} e^{-j\omega_1 t_o} = Ae^{j(\phi_1-\omega_1 t_o)}$$

Where $\omega_1 t_o$ represents a constant phase shift or rotation.