The media content for Walkman app is provided by Android Media Storage Service. You can delete the non-existing songs and playlists by going to Settings, Apps, All Apps. Find the Media Storage service, tap it and select Clear data and Clear cache.
This will erase all the information about the media content in your phone and force Android to re-scan the content in your phone memory and on SD card.
For a few minutes you will not see any songs or playlists in your Walkman app. Then, suddenly, new information will be displayed. Many erroneous entries will not be any more and the information will be more accurate.
