I like to use music as an addition rather than a focal point, so I usually do it last. Sort of like adding sound effects; once you know where everything in the footage belongs, you can add effects accordingly. Doing the music last (or just before the final edits) helps me to (1) not have the distraction of music over the video and (2) to be able to find a track that fits the mood of the final cut as opposed to working the final cut around the mood of the song.
Then again, I tend to do more vlog type videos whereas you make compilations of footage put to music. It makes more sense for you to add the music first

I love how we all have our own styles, though! We're all unique both in what we do and how we do it