When asked about how "masterworks" are created, Nadia Boulanger, a French composition pedagogue during the 20th century, had this to say:
"I can tell whether a piece is well-made or not, and I believe that
there are conditions without which masterpieces cannot be achieved,
but I also believe that what defines a masterpiece cannot be pinned
down. I won't say that the criterion for a masterpiece does not exist,
but I don't know what it is."
Of course, the original question is specific to wonderful melodies, but really, melodies are no different from the composition process than anything else, and much like the composition process varies greatly from composer to composer, so too is the fickle creature of inspiration ceremoniously wrangled and subdued for a moment.
For composers like Mozart, Mendelssohn, and Schubert, writing was very easy and came intuitively. Other composers like Beethoven, Brahms, and Joan Tower labor relentlessly, tearing themselves asunder in the pursuit of their art.
Brahms once wrote that he would have given anything to write the melody for the Blue Danube Waltz, yet he wrote the "lullaby" melody we all sing when we are children.
Scriabin described writing as if he was looking behind a mystical curtain into a land of unfathomable possibilities. Picasso described painting like vomiting and indigestion. It has nothing to do with music, but I find his description hilarious.
As other answers have pointed out, musicians are drawn to sounds around them - whether naturally occurring or synthetic. We spend out lives dealing in sound. So, the lady speaking Japanese next to us that you're tuning out? Yeah, I'm distracted. Instances like the one I just mentioned may be attributed to the theory of multiple intelligences, for which I am a solid proponent.
Just like you deal with visuals daily and naturally understand balance but are similarly confused by music composition, so easily would a musician be able to respond as acutely to your profession in kind. It's just what we do.
When people have heard a piece of mine for a large ensemble, let's say an orchestra, they might say to me afterward, "How did you think of all of those sounds? How did you hear all of those sounds?"
Much like drawing, architecture, painting, or other mediums, you start with broad strokes, broad sketches, and gradually add more detail as things progress. It happens in layers and it does not happen from left to right - much in the same way you do not sculpt from the top to the bottom of a piece of rock in complete finished detail.
In my comment, I alluded to waiting for inspiration and audiation, which I will discuss further in the next page break.
Though you talk about melodies in your question, your question is actually about inspiration. I will limit the scope of my answer to address melodies, though my comments may be extrapolated to include other elements as well.
Inspiration for Melodies may be evident is several forms:
- External Stimulus (elevator, siren, cell phone)
- Internal Stimulus (self-hearing -> a.k.a "audiation")
- Pre-existing from a composer's scrap catalogue
- Pre-existing from a composer's previous complete work
- Pre-existing from another composer's previous complete work
- Aleatoricism (chance operations)
- Serialism (order and control)
- Pure Compositional Exercise (using theoretical knowledge)
This list is not comprehensive, but should provide a good foundation. I believe most of the above items are self-explanatory, but I will briefly describe aleatoricism and serialism further.
Aleatoricism is a process by which composers alleviate themselves of control and allow the universe to "choose" for them. Essentially, it is the same as flipping a coin. This style largely became popular with the New York School in the mid-20th Century with John Cage, but scholarly research supports that even Mozart played dice games not only to write melodies but also to decide on how to order sections within his pieces.
Serialism by contrast, the complete opposite. In this style the composer can assume total control over pitch, rhythm, dynamics, articulations, etc. Music in this sense can be essentially manufactured, and several composers became very, very famous for doing it - albeit for different reasons.
Now that has been covered, I would like to add here that composers also frequently make decisions while they are working on pieces. A composer may plan for a piece to go a certain way, but in reality, when playing their work back at the piano or on a computer, their ear may be leading them in a different direction. This type of filtering procedure interferes within the original germinal idea, but it is necessary and good and saves composers from writing a lot of bad music and audiences from hearing a lot of bad music.
Here is the bottom line, and you probably will not like it:
To compose a melody is to create art and no one, I repeat, no one
yet fully understands how human beings write the music we do - from
germinal idea to finished product. The process for each individual is
unique contingent upon their personal and artistic aesthetics, their
culture, and their upbringing. Within that, each piece is unique and
special to each composer, like a small child.
We appreciate the art because we do not understand it and it is
foreign to us. If there were a store to purchase manufactured
melodies, art would be devalued as the depth of its meaning has been
translated to tangible, worldly goods, and therefore speaks little of
time, passion, and commitment. It is the same reason why homemade
food tastes better and handmade gifts more sentimental.
Unfortunately, I cannot tell you exactly how "great" melodies are written, because by no fault of your own virtue the question's scope is philosophical and too broad to answer simply. However, I have described some of the ways and techniques in which composers operate, which should provide a clearer understanding of the question as well as your own pursuits.
As an aside, I have written fairly extensively on this topic and would be happy to discuss in greater detail via chat.
Best of luck.