Here is a great tutorial for using a hall sensor for a fan that runs at 3400 RPM. It counts the amount of trips from HIGH-to-LOW to register as a rotation (assuming the magnet is connected to a point on the rotating shaft that goes out of range of the hall sensor).
Here is the tutorial:
Arduino Tachometer - Using a Hall Effect Sensor (A3144) to Measure Rotations from a Fan
Here is the hall sensor used:
