The songs themselves are ok right? Just add them to iTunes "after" you've finished recovering the erased files.

Do you have another partition on your system with any spare space? If yes then recover the files to that partition not the original. After recovering all you can, then add them to iTunes (control & O keys within iTunes.) What other storage devices do you have? An external HDD or another computer or a zip disk or something similar? Utilise what you have. (No need to move the files you've already recovered back to Drive C because they won't do any more harm there for the moment.) Oh & your old .m3u playlist files are probably not worth anything now anyway so just concentrate on the mp3's. (Playlists are simply references to the whereabouts of the songs ... playlists do not contain music themselves.)