rotary hall effect sensor and working with the arduino

Ok First off i'm super new at the Arduino and my mind works better mechanically than electronically. back round on the project i'm attempting to do i have a older muscle car that kind of a resto-mod car i've got one cooling fan that is electrical i don't run a mechanical fan off the motor. now when i'm sitting in traffic i have to have the fan running but when i'm cruising down the road i don't need the fan if fact i think the fan at some speeds is just spinning. so now comes the the question i have a rotary hall effect sensor that hooks up to my digital speedo its a 16 pulse per revolution sensor. my thinking is using a Arduino to count the pulses to X in a certain time frame. so say i'm in my car and i'm driving 50 MPH say this would equal 20 DC pulse a second. could i program the Arduino to count the number of pulses a second if the number is higher than 20 the relay is turn off and the fan doesn't run. if the count is lower than 20 the relay stays on. my worry is that the signal would be hard to read at high speeds and maybe need to be de-bounced. I'm open to suggestions this is the only thing my mechanical mind could come up with. there maybe a simpler way. thanks

You haven't said, but I presume your fan is for cooling your radiator. If so, why not use the water temperature to switch it on and off? A thermostat (a bimetalic switch) will do that for you, without using an Arduino. That's what's in most cars.