You can delete them all at once with mass storage mode. When hooked up to the computer with the usb cable you should get two drives representing the device memory (blackberry1) and the media card memory (blackberry2). Just go to the music folder of the drive where the music is stored, then select and delete all the songs.
Posted from my CrackBerry at wapforums.crackberry.com