IMO, the exact order to learn scales is dependent on what kind of music repertoire you want to learn. If you want to learn piano music, you start with C major because it uses (the generally considered "easier") white keys only. If you want to learn guitar music, I suspect you start with G major because the strings are typically tuned to play it better than C major. If you want to learn concert band music, you start with B flat major because enough important (transposing) instruments treat that as their home key (such as the trumpet and the clarinet).
Due to difficulties in learning minor scales (for each minor key, you need to learn both the harmonic minor and melodic minor scales), I've actually generally been exposed to a learning pattern that's more like this (at least for piano--transpose all scales down one whole step for concert band):
C major-F major-G major-A minor-D minor-E minor-D major-B flat major-B minor-G minor-...
While I do not recommend picking songs completely randomly in order to learn scales (you risk running into songs that change keys far too many times, atonal music that is not in any key, world music that does not use major or minor scales such as gamelan, and more), picking a sample of a lot of songs, then learning the most common scales first, is a wise idea.
Along those lines, I do not recommend learning all major scales before all minor scales, as some major scales are significantly more relevant than others. In concert band repertoire, for example, songs originally in keys with several sharps (e.g. E major) are often transcribed into versions in keys with flats instead (while B flat major, F major, and E flat major are common targets because they are the first few keys that students learn, this transcription of Dmitri Shostakovich's Festive Overture in http://www.jwpepper.com/599043.item is in A flat major instead of the original piece's A major). In another example, you bump into some keys more than twice as often as others on Spotify, according to https://insights.spotify.com/us/2015/05/06/most-popular-keys-on-spotify/.