If you stop listening to songs, eventualy the odds of fragments of song poping in the mind would shrink, but is that realy what you are looking for ?
A better way to approach this would be to let go of the aversion you feel toward having songs beeing replayed in your mind.
When it occurs, do as you do with any other distraction or thought. Watch is appear and disappear by itself, watch for any sensation or thought that may arise because of it.
Even if you decide not to listen to music anymore, you will be exposed to it against your will from time to time, so you can't really count on "dropping the listening habit" strategy alone.
Please also consider that one can listen to music in order to feel sensual pleasure, which is unskillful, but also to engage with a particular art form which won't prevent your spiritual growth at all. See this question Buddhist view on Art and being an Artist.
Music can increase one's motivation in his spiritual developement, by giving access to particular emotions one would have never felt otherwise.
Just a few examples on the top of my head :
If you are on a bad day, listening to a particular song could uplift your mind and give you the motivation to sit and meditate.
If you have trouble feeling goodwill towards other human beeings, try listening to Beethoven's 9th symphony. Also 5th symfony can easely be interpreted by the story of a person who gradually overcomes his bad kamma. 6th symphony is about joy associated with nature. And so on.
As with any other actions, you should contemplate the effects of listening to music. With time you will build up discernement, and avoid situations when listening to music is unskillful.
Be good to yourself and don't beat yourself over it unnecessarily. When you see clearly the drawbacks of music, things will resolve quite naturally.