Ultrasound is an audio signal like any other, so relative movement can be detected using "normal" sonar methods.
Now, Andrew mentioned that
I'm not aware of cheap ultrasound sensors that can measure the Doppler in the return signal.
Neither am I, but:
Producing ultrasound is no rocket science.
In fact, there's plenty of >= 40 kHz "audio" actuators readily available on the market, and most of them double as sensors (transducers), for less than 10€.
You could easily produce a working transmit tone (e.g. by using a sound card to produce a 5 kHz tone, and by adding harmonics through nonlinear amplification, simply by feeding that signal to a bipolar transistor, and then filtering out everything but the 3rd order overtone, i.e. 8 times the original 5 kHz == 40 kHz), amplify that tone sufficiently much to drive your transmitter, receive the reflection with another ultrasonic transducer) and use an ADC (e.g. a soundcard again) with removed anti-aliasing filter, so that the 40 kHz +- Doppler Shift end up being aliased. Undersampling! Simply multiply in your PC with the "original" 40 kHz (account for the fact that this tone aliases, too), and you should see the Doppler frequency shift as tone. Done!
If you don't want to use a PC, but rather do everything with microcontrollers, things can even get easier, as producing a 40 kHz square wave can usually be done with a simple PWM unit, and that square wave can be filtered to a sine simply by a very easy RC low pass with a cutoff somewhere between 40 and 80 kHz. Use that sine both on your transmitter and on one of the mixing inputs of a SA612 mixer IC. Connect the other mixing input to your amplified received signal; filter the output of the SA612 to remove DC offset (easy - coupling capacitor) and frequencies above the doppler shift you'd expect.
Now all you'll have to do is to determine the frequency of the mixer's output. That can be done by specialized ICs that convert frequency to voltage (e.g. LM2907) and ADC'ing that, or simply by using a comparator (or equivalently used opamp) to convert the sinusoidal output of the mixer to a logic signal, and using the microcontroller to count the edges in a given time window (in fact, many microcontrollers have extended PWM features that do just that in hardware – no programming/CPU cycle overhead).
Also note that it might be beneficial to not use the exact same frequency for transmission as for mixing – if you use something different, you'll get your "undopplered" response somewhere else than DC, and will have an easier time telling positive and negative Doppler shifts apart. You'd be building a superheterodyne receiver, by the way.
All that's left to be done is converting frequency estimate to speed estimate. That's simple math.