Try:
locate --print0 *.mp3 | xargs -0 -n 10 echo
I'm not sure if it will work. It works here in small scale, but when I push the whole locate trough, it gives a error msg. Anyway, the --print0 option sends a ascii0 at the end of the filename, and -0 option on xargs uses this null as a argument seperator. Finally -n limits the execution to 10 files at a time.
If it works, change echo with rm