Perhaps you can use a CNY-75B or similar opto-isolator and simply have the hall effect transducer on another voltage rail.
I used this technique going the other way, to drive a 12V fan at a desired rate: http://my.grumpykitty.com/2011/04/arduino-freertos-fan-rpm-video/
My input to the arduino was analog, but it seems like the CNY-75B would be generally useful for I or O. It's just a small chip that acts as a transistor but with the gate at a different voltage to the collector and emitter.
You can download a sketch for the rpm counter using a neat little timer library someone made public, and the temperature controlled fan is in C++ using FreeRTOS (not the recently posted DuinOS, and caution - I ran out of memory using it!).