My 25Mhz 68040 has problems trying to play mp3's but it can do it... my 50Mhz 68030 simply can't do it real time.
So I would say the 040 is the lowest spec for mp3 decoding.... but we all know how hot and hungry they are, so you might want to look at a Coldfire... but that's another thread. :-D
ON the other hand, if you know 68K asm, simply rewrite what you have for a CPU much more suited to the mobile environment... it you want to do it cheap, might I suggest a microcontroler and a DSP combo, that would give the best characteristics for an mp3 player.... I suggest you choose a microcontroller which supports Compact Flash so that you can use cheap removable memory cards.