makerportal:
Here is the hall sensor used:
Hold a regular magnet in front of the sensor, it will read according to how the poles are placed? So set it up to read 1 or 0.
Now put some sheet steel between the magnet and sensor, a steel food can should do to block the sensor.
Next find out how small a hole in the metal will let the sensor detect the magnet.
If you put a circle of holes or tabs on the spinning part that a magnet and sensor on an arm could sense/not-sense through then you could have many reads per rev.
Hold the magnet behind a linear Hall sensor and any moving metal in front will change the field, how gear tooth counters work.
Or shine IR through the fan and detect that between the blades.