I can find no single origin point for this never-uttered catchphrase, but I would hazard that it's a natural mutation of several similar phrases, the closest being a command directed at Spock instead of Scotty:
KIRK: Beam me up, Mister Spock. (From "The Squire of Gothos")
This could easily have become blurred with the various forms of this command issued to Scotty, such as
KIRK: Scotty, beam us up fast! (From "The Savage Curtain")
etc., as well as a couple instances of
KIRK: Beam us up, Scotty
coming to us by way of The Animated Series (for example, as heard in "The Infinite Vulcan").
The earliest instance of "Beam me up, Scotty" I can find in print is in Volume 79 of The Aeronautical Journal, published in 1975:
...cliffs, fire, forest or mountain is most probably some form of transporter device such as that used by Captain Kirk and the crew of the starship "Enterprise" — a sort of "beam me up Scotty" routine. However as this is still in the realms of fantasy...
That this is the origin of the phrase is possible but highly unlikely — it almost certainly existed orally amongst the public in the late 60s during the run of TOS itself.