This might seem like an easy step, but having learned how to recognise all the intervals upto an octave: ascending, descending and harmonically, how does one figure out a melody by ear? I can pick out a melody with a few wrong guesses but I just can't seem to figure it out on the first try in the way I can with intervals. Should I be relating each note back to the root, or to the previous note in the melody?
Short answer: more practice.
Longer answer: learn to hear scale degrees relative to the tonic i.e. home note, not only relative to the previous melody note. And for this it's very good - I'd say almost essential - to be able to accompany the melodies with basic chords by ear, and to know the function of each individual note in the chords. For example, after you can distinguish the dominant i.e. the V chord, and you can arpeggiate the notes of the V chord in your mind, it will be trivially easy to recognize the 5th and the 7th note of the scale in a melody. So, don't play only melodies, play melodies and chords. Playing chord notes will support your melody recognition skills, and playing melody notes will support your chord recognition skills. I think they both support each other.
Good strong melodies are usually built by playing chord tones on strong beats, so you can think of a melody as flashing or revealing parts of the implied chords. When you try to play a melody by ear, you're actually trying to hit its chord tones, you just don't know it yet. :) Or more like, you're trying to grope or feel the chords with your eyes closed. When you play the chords and the melody, it's like opening your eyes or turning the lights on, so you see what it is you've been groping. (at least from one possible perspective)
Play and listen more, much more! Knowing intervals is a good thing, but being able to hear, say, M6 and recognising it is half the battle. You need to minimise the 'ah, it's a M6' to just hitting that M6 above the last note played. Be able to play M6 above any note anywhere in any key! Rather like when you learned piano, look at note; it's F#; find F# on piano; play it. Cut out the middle process.
Being totally aware of the underlying harmony helps greatly. Knowing which notes constitute which chords will give good clues as to what the phrase at that point will contain. The chord will almost inevitably contain notes from that part of the tune. Or, conversely, the tune will contain chord tone notes. Makes sense. Over a C maj7 chord, the notes which fit best will be C E G and B. Especially on the pronounced beats of a bar - 1 and 3 in 4/4 time. Worth checking this out on dozens of songs - check the chord in a bar, check which notes go with it.
Armed with that info., finding, playing and remembering the notes in a melody will become second nature.
Most people can learn a melody without knowing which notes there are, also the rhythm can be reproduced not necessarily notated.
Identifying the tones may be achieved interval based or root tone based, but also by recognizing the lead tones fa-mi, ti-do, ta-la, si-la.
A big help will be knowing typical chords like augmented triades, (domisi), diminished triades, minor and major triades.
The best is when you can keep the tonal center in the short term memory and the fifth. Check the final note.
A good start for learning melodies is a repertoire of typical beginnings of a dozen of songs.
As you didn't mention in your question the Solfege-Practise I wonder whether you are aware of it:
This is nothing else than ear training by singing the chords, training usual chord progressions and melodies:
You can learn to sing (or follow/analyse by your inner ear) whole concertos and solos singing (or thinking) the notes.
I trained this by learning the inventions by bach and preludes by heart and minding them connotated with the syllables of doremi. The same I'am practising with the Concerti grossi of Handel, the Brandenburgian Concertos, Haydn's Trumpet Concerto and with each piece I have to learn new. The best is when you practise thie with a tuning fork so that you always are in the right pitch too.
You can do this when laying in bed, or when you are on a tour or when you are swimming or listening to music.
You will see that suddenly that the system of solfege (doremi) will function automatically and unconsiuosly as a concitioned reflex. So one day you will recognize melodic patterns when you listen to music ... without minding or thinking.