The way music copyright works, it's possible it's done in a completely-legal way.
DMCA takedowns are targeted at specific recordings. The Cohen estate (or whoever they have managing song rights) can tag Leonard Cohen's recording of the song on Youtube, but not any of the multitude of covers that have been recorded over the years. Each recording of the song is its own copyright, and that recording's copyright owner would handle that (if they care).
Once a song is released, you don't need permission to record and distribute your own cover of the song. The publisher is entitled to a royalty as rights to the mechanical aspects of the song (melody, note progression, lyrics), but they cannot issue a takedown over it unless all other attempts to collect that royalty have failed.
There may very well be a musician who recorded the song as an instrumental piece and released it to the world as an open license.
Or, ever safer for Selebus, he could have comissioned a recording from someone specifically for this purpose. This way, the royalty burden is on the musician (and would likely have been figured into the commision's cost), and there's no murkiness to navigate. Frankly, if I were developing a game, this is how I would handle the entire soundtrack.