It probably doesn't need to do an FFT, it just need to be able to count beats and have a database of BPM values for popular songs. You could use something like

It probably doesn't need to do an FFT, it just need to be able to count beats and have a database of BPM values for popular songs. You could use something like AcoustID/Chromaprint to identify the song you're playing. A very simple idea, as all the best ideas are.