It had indeed, but we're talking about incredible differences of scale here. At the time of the Edict of Milan, Christianity was orders of magnitude smaller than it was less than 70 years later, when the Edict of Thessalonica was signed. As Kerney mentioned, it had spread from around 5-10% of the population at the time (after almost 3 centuries of spread), to very likely majority status, all in record time. There's no reason to think that, left to its own devices, Christianity would continue to spread and spread and that it didn't have a natural ceiling that was lifted by getting the backing of the Roman state and thus the quick adoption by Roman elites.Yet it had been growing for three centuries even *before* Constantine.
Mithraism was itself a pretty niche cult almost solely popular within the rank and file of the army. The worship of Sol Invictus was not an exclusive religion-Sol Invictus wasn't being worshipped to the exclusion of all the other Greco-Roman-Eastern gods, but as the head of that diverse pantheon. So it's not really worthwhile to ask "how far had the cult of sol invictus spread when it was promoted by Aurelian?" Most Romans would have believed in a sun god, whether they called it Sol Invictus (or Jupiter), Elagabal, Helios, or whatever.Hadn't Sol Invictus been around (and enjoyed Imperial favour) long enough to bring up a second generation? Mithraism certainly had. Didn't stop them being dislodged when Christianity came along.
Was there any rush to worship Elagabalus' Sun Stone when he became Emperor?
But since you mentioned Elagabalus and Sol Invictus in the same post, I will point out that there's a popular current of scholarship that believes the prominence of Sol Invictus in the third century actually is in large part related to Elagabal being brought to Roman prominence by Elagabalus. While there was always a small cult of Sol in Rome, it was relatively muted until the third century, after Elagabalus (The Historia Augusta, I should note, eequates Elagabal with Jupiter and Sol, these gods were in effect treated as one). The Sol Invictus cult that Aurelian organized specifically is likely heavily based on Emesene Elagabal.
So to answer your question, yes, actually, the Sol Invictus/Elagabal had in fact spready remarkably fast in the third century since the introduction of Elagabal to the Romans. It's just that worship of Sol/Elagabal was not an exclusivist religion.