A digital hall effect sensor will give you data as either on or off, great for counting rotations.
15,000 RPM leaves you over 60,000 operations between pulses on a 16MHz Arduino, so that's a very easy range to measure very accurately.
You will need to make a collar for the shaft that has a magnet in it. As the magnet rotates with the shaft and passes over the hall sensor it will raise the output pin of the sensor.
I'd use an interrupt to increment a counter. Then read the counter - last counter reading to get rotations over time.
I wrote this in the browser so check it carefully, but I think this will do the job.
It could be made better but I think that will get you off the ground.
I knew I missed a thing or two.
That's what I get for doing it from memory.
Thanks for the correction.
Would you mind fixing it for OP as I'm on my phone now?
If you use say an Allegro type A3144 and place a small magnet on the back of it, the hall will register pulses as the gear teeth pass.
These are available as a module with a built in led and resistor so no pullup required.(Ebay etc. KY-003)
Note that you need to use a pullup resistor on the hall effect if it is a discrete device as it is open collector.