The songs are stored in the location that is set in whatever you used to get the songs onto the device, common locations are in the music folder on either the internal or external SD card, some apps like Amazon mp3 have no options for save location & it puts them in a folder under it's own. Deleting a song from within a player app also depends on the app and/or settings, if it set to just delete from play list it will still be there for the other apps, if it's set to delete from device the song will be gone. I don't like either of those apps, I use power amp, I also like n7 player. If you store your music locally those 2 apps plus some other are generally a better choice, my music supports streaming from motocast, play music supports it from Google, and others support from various other sources. Pick the app that meets your wants/needs.
Sent from my DROID RAZR using Forum Runner