I'd say long before under the Stagecoach Express banner, maybe the 80's/90's? Think Citylink ran England-Scotland Cross Border services as well!
Was thinking specifically under the Megabus brand, was it a direct replacement for a Stagecoach Express branded service? But with anew brand and, of course, the ‘from £1’ fare structure.
Not quite. The "Stagecoach Express" branding didn't appear until the 90s and was used for interurban services. Bluebird's 305 (now 35) route used it, as did a few routes from Fife to Glasgow and Edinburgh. I'm sure it was used elsewhere, but I don't recall.
Stagecoach's original long-distance express services were simply branded as "Stagecoach" and were sold off to National Express in 1989, with coaches carrying a modified National Express livery and "Caledonian Express Stagecoach" branding (the Stagecoach name was licenced to National Express for two years).
Cross-border services were traditionally operated by a few Scottish Bus Group companies, initially under their own branding, then under the blue/white "SCOTTISH" brand before being brought under the Citylink banner. Stagecoach was originally set up to compete with these services and numerous other operators have had a go over the years. This is definitely a subject for a separate thread, though.
Megabus was an entirely new concept that began in 2003.