PWM & output voltage
I think you're being bitten by the physics of the fan.

The power in a stream of moving air is proportional to the cube of the air velocity, and the rotational speed of a fixed pitch propeller (i.e., fan) is directly proportional to the air speed. This means that to double the air speed from your fan (or its rotation rate), you have to put in eight times as much power. Or conversely, to cut speed in half, you only need an eighth of the power. If you call the air speed you get at 100% duty cycle 'full speed', then 'half speed' will occur at 1/8th the power level; at 12.5% duty cycle. Even more dramatically, quarter speed would be at 1/8th of that, at just 1.5625% duty cycle. In other words, whatever speed you get at the very lowest duty cycles is nearly all you're going to get, because power in moving air is so non-linear.