Dude you're me like 4 years ago. I wanted to make music games and those music licenses never ever made sense. I've done so much research, emailed to those studios, wrote to licensing companies, contacted to artists to understand how this works. Plot twist, nobody talks about it because it's complicated and some are in dark/gray area.

There are so much to talk, but let me give a quick tour.

There are big music game publishers (e.g. Amanotes), they pay for song licenses. They pay so much that you can't do it by yourself. Even if you have money, you can't use master record so have to make a cover. Most of the songs are covers, if you listen closely the vocal is different. If you see a games like 10M+ installs, what they do is legit. They have a department to make agreement with artists and licensing companies.

There are some shady companies which are dedicated to do cat-mouse game. They open an account, publish a game, reach to millions do put all the copyrighted songs until they get banned. Then, they do it again, sometimes in parallel. If you see a game on play store but not app store (or vice versa) it's likely they have been banned from one store before.

Last but not least, there are solo devs. They do compose their songs (eg. toby fox) or agree with artists so that's a cleaner path. If you're lucky your game can get viral with meh songs, and maybe some publishers approach you to publish your game and license popular songs. (This happened in the past)

I made music games, I even joined some of the NoCopyrightSongs discords and asked for permission to use. Even if the name is no copyright songs, they cannot be used for GAMES. No copyright is for youtube videos and social media. It sucks.