The fastest way to unlock every song in the game and keep them is to do the Decades Challenges in Tour Mode. You'll have to play an instrument intro challenge and then one challenge each of 60's, 70's, 80's, 90's, and 00's challenges, with 2-6 songs apiece (usually four). Once you beat a Decade Challenge, the Decade Marathon will unlock which contains every song from that decade (enabling them for Quickplay). So, play six setlists (about 24 total songs) and you've unlocked every song. Shouldn't take you more than a couple of hours, much faster than slogging through Tour Mode.