I'd look at the formats that the device supports.... but in most cases mp3 or aac would be the best option although windows phone doesn't support aac.
What format are the files in now... aac can compress to roughly half the size of an mp3 for example and a cd (650MB for ease) can compress down to under a hundred megs.
Software - as daft as this sounds, itunes...
yeah in essence, back them up then run it through itunes import after it's been set to aac, you should be ok with 64Kbps with aac verus 128Kbps in mp3 without any real noticeable loss, although you can try 128Kbps.
I've done it with audio files but I can't vouch for it working obviously as I've never done an app but there's no reason why it shouldn't.