Does the frequency of a PWM signal have to be constant for a DC motor/fan speed control?
The frequency need not be constant, although it often ends up this way because it's easy to implement. One reason to vary the frequency is to spread EMI and audible noise across the spectrum. It's also possible to perform motor control by hysteresis. Or, the pulse width may be held constant but the frequency varied. Or, both may be varied.

What's really important is average voltage being applied to the motor over time. In the case of a simple DC drive, the average voltage is the same as the voltage applied at any instant. Usually, the voltage switches between 0 and the supply voltage \$Vcc\$, so the average voltage will be somewhere between 0 and \$V_{cc}\$, according to the proportion of time spent on \$t_{on}\$ in some period \$t_{total}\$:

$$ V_{avg} = V_{cc} \frac{t_{on}}{t_{total}} $$

So if over \$100mS\$, you spent a total of \$40ms\$ on, and \$V_{cc}\$ is \$12V\$, then:

$$ V_{avg} = 12V \frac{40ms}{100ms} = 4.8V $$

So, to the extent that the inductance of the motor is able to average the current over \$100ms\$, you might as well have been applying \$4.8V\$ DC to the motor.

This is what sets the lower bound on the drive frequency. If the frequency is too low, the current in the motor windings (and thus, the torque, and thus, the speed) will not be constant. Take an extreme case: you apply 12V for 4 minutes, then 0V for 6 minutes. The average voltage is still 4.8V, but obviously you don't get the same effect.

As the frequency becomes higher, the maximum current (right before switching to the off state) and the minimum current (right before switching to the on state) will not be very different, and the motor current is mostly constant. This is because the rate of change of current \$I\$ in an inductance \$L\$ is limited by the applied voltage \$V\$:

$$ V = L\frac{\mathrm{d}I}{\mathrm{d}t}$$

or equivalently:

$$ \frac{\mathrm{d}I}{\mathrm{d}t} = \frac{V}{L}$$

Your power supply can apply only a finite voltage to the motor windings (an inductor), so the current can only change so fast. Switch fast enough, and the current never has time to change significantly.

Another way to think of this: The current in the motor will have some DC component, the average value that spins the motor in the desired direction. It will also have some AC ripple added to that, which just makes heat in the windings since it spends half its time spinning the motor in the desired direction, and the other half in the wrong direction. Your goal, in designing a PWM motor drive, is to reduce the current ripple, and the consequent wasted electrical energy, as much as possible, without increasing other losses in the system.

Another requirement is often that the motor not make audible noise, and this often requires that the switching frequency be above the limits of human hearing, about \$25kHz\$.

The upper bound on switching frequency is set by losses that increase with frequency, primarily switching losses. Transistors can not switch instantly, and so will necessarily spend some time with both significant current in them, and significant voltage across them, thus converting electrical energy into heat (\$P=IE\$) each time they switch. As the frequency is raised, the number of switches per second increases, but the time spent transitioning from on to off states says the same, so the average power in the transistor increases until the heat destroys the transistor or the driver efficiency becomes unacceptable.