I have 40,000 songs. Every track legally obtained. Starting with about 650-700 CDs (the total lifetime collection of my wife, myself, plus some given to us by friends who didn't want them anymore), got me to around 12,000 tracks. I've purchased about 500 sings directly since, plus the free Tuesday tracks every week going back years.
Then there came Stream Ripper. Tune to a shout-cast station (or other similar feed) that broadcasts "space" between each track and let it run for a few days. It automatically separates the files and names them based on the track titling, and detects and deletes duplicates. For a while i was ripping 4-6 concurrent 256bit feeds, adding half a thousand new tracks a day. It is not illegal to record a broadcast that is free to receive. Modern stations limit easy record-ability by using voice-over, cross fade, etc, under pressure from the RIAA, but in my music preferences, I could care less about Pop and Top 40, so finding stations that ignore RIAA requests to limit recording is easy.
I've not run it in a while (after a few weeks, finding new tracks becomes less and less frequent), and it;s probably time I turned it on again. I run it a few days once every few months and catch a few hundred new tracks, but finding good stations is harder and harder to do.
Anyway, 40,000 songs is far from improbale, or impossible, to do legally. Hell, i know some people who have bought 2-3 new CDs every week since the mid 90's and could legally own that much music through purchase alone.