Beats per minute calculator
To do any good, you will have to sample the audio at some set rate (usually at some thousands of samples per second.)  You can  find out how many samples per beat you have and calculate from that to get the beats per minute.
As others have said, though, this isn't really a job for a little ATMega.  To do the job with any kind of accuracy, you will need to do some pretty hefty signal processing - an 8 bit processor at 20MHz is not going to do it unless you are an absolute DSP genius who can find a new, unbelievably efficient algorithm and implement it on an 8 bit microprocessor instead of a DSP.

If accuracy isn't important, you could do as you planned (detecting peaks.) The number of samples between peaks can be used to calculate the BPM.
Say you are sampling the audio at 8000 samples per second, and you find the peaks are 4000 samples apart.  That would 2 peaks per second, or 120 beats per minute.

As you already know, though, the simple method of detecting peaks will get you a lot of false peaks.  You might be able to reject peaks that are too close together, but you should be prepared for the results to be pretty lousy.