Yeah, but the idea that the timeline hasn't been replaced flies in the face of every time travel story Trek has in its canon, going all the way back to "Tomorrow is Yesterday," reaching its apex early with "CotEoF" and and continuing through such TNG episodes as "Yesterday's Enterprise" and the DS9 two-parter where Sisko "becomes" Gabriel Bell ("I don't like your hat! And I don't like your attitude!") and, I'm sure, eps of VOY and ENT that I'm not fully familiar with. Time travel within a universe results in altered timeline within that universe. But Trek has canonically established parallel universes and time travel between dimensions. The party of me that likes to play with the silly SF concepts of Trek is just pointing out that the latter gives us the ultimate "Get out of FAIL free" card.
The Mirror Universe wouldn't be possible under standard trek guidelines, and Parallels was used as the travel framework for the movies. Time travel is one thing, parallel universes are another, but mixing the two is something else entirely. Parallels showed us hundreds of thousands out of an infinite number of possibilities, this movie being one of them.
Something tells me that if someone went back in time to prevent Zephram Cochrane from ambushing the Vulcan first contact team, it still wouldn't erase the beloved Mirror Universe.
And in sci-fi, there's ALWAYS a Get Out of Fail Free Card

Alternate universes, sonic screwdrivers, the Force, Mr. Garbage, etc...