You should give the hardware way a try first. The less your arduino card do to clean the signal, the more features you can to your program...
I've previously thought about a similar feature (being able to measure the speed based on a hall effect sensor). One of my lead was using a frequency to tension converter. Thus, no need to deal with interrupts, just have to read an analog pin.