I actually do it a little different from what's been shared here. I tend to start by trying to figure out the bass (the root notes at least) and from there get the chord progression and key of the song. In my opinion, you get a lot of useful information from a song from just this. Melody is important of course, but a ton of VGM songs tend to play around the chord notes so, once you know the chords, the melody comes easy.
When it comes to actually writing a remix, I tend to learn the song and then just sit down and improvise. It helps if you have a predefined idea, like, "make a metal cover", but usually just playing around with the melodies and chords is enough to trigger some inspiration.