An interesting question......
They come in many different ways.
Some of it depends on the main instrumental thrust of the song. I write on bass, guitar or in my head without an immediate instrument to hand but I'll fill in the melody with some imaginary back up which I get quickly into the dictophone.
I've long found, since I first picked up a guitar and put two or three chords together, that no matter the order of chords, a melody would suggest itself to me. Whereas it was years before I could put melodies to my bass lines, the guitar ones came straight away, moreorless. That may be because I could sing and play guitar at the same time but I've very rarely been able to play bass and sing at the same time.
I used to struggle to come up with melodies, often an entire song would be recorded and the melody would strive against that and melodically, there'd be so much going on that the melody would be drowned in a sea of mud. I find that now, as I'm imagining the music, I go left field, melodically, just roaming randomly. And something always comes. Often after a recording session as I'm listening back to what's been done, a melody or instrument line will suggest itself. I have to hum it into the dictaphone because I'll forget it otherwise. And it might be months or even years before I return to it and it's not always clear where I was going.......
Just keep playing around with your music. I'm confident enough to know now that something will come. Sometimes I take what I think of as a safe predictable route and it's not until the vocal has been recorded that I realize how weird it is.
And some of them are just plain hard work, like pulling teeth. Then they get easier with successive listens.