I think you could argue that melody first is almost always correct. Even sub-consciously, you are thinking of a melody in your head and how you want the song to go. You can't have music before melody I don't think. As you are writing music, you are writing out a melody you are thinking of. Lyrics first would be the only other alternative.