I had this happen with an iPhone a few times. The only way I could get rid of the songs was to restore the phone. You might want to try that if nothing else works unless you are jailbroken. The iOS has a few bugs with this for sure.
This happened to me whenever I got my iPhone last year and it was restoring from the iCloud backup.
What happened was that the songs I couldn't delete and kept popping back up were being downloaded from the iTunes app from my phone. All I had to do is wait for those to finish downloading and then I was able to delete them.