wondering if the issue may be what amounts to noise on the sensor, thinking being if when the blade doesn't turn you (correctly) read zero, and at max you get pretty much the correct answer (I suspect you may actually be slightly over reading) and lots of over-reads in between I'm wondering if you have more errors at lower speed.
in effect is the sensor gittering across its threshold for a time, a time which is lower the faster you go.
easy to test, turn the fan blade very slowly by hand and have the interrupt set a flag so you get a serial write when (or shortly after) it fires - if you get multiple triggers as the blade with the magnet approaches the sensor this could be the issue.
not hard to solve, stick a Schmitt trigger or similar fast acting de-bounce type circuit in.
have had similar with photo-interruptors that are meant to be a hard yes/no output and things moving into the field of view at lower speeds, sometimes its better to run a linear output sensor and put the hysteresis in yourself to tune to the application.
just a thought?
curious as I'm currently doing something pretty similar (measuring fan rotation as a proxy for air flow), planning to use IR LED/Phototransistors as I have them, I do have a hall sensor and the fan actually has a magnet & hall speed sensor built in - which I'm testing the function of.