Assuming everything else in Emplode works, are you sure you're really deleting the songs as well? Just deleting playlists doesn't delete the actual tracks.

Emplode normally prompts if you want to delete the tracks as well. You have sync'd after editing in Emplode, right?

Sorry if I'm stating he obvious, but from personal experience I know it is the obvious most of the time with me being the stupid one .