A number of major Broadway musicals have been translated into Russian: Jesus Christ Superstar, Chicago, and Cats come to mind.

And some of the songs from these musicals became popular radio hits, so your karaoke guy probably has them on his machine: "I Don't Know How to Love Him" and "Memory," for example.

So, you might be able to find the Russian lyrics online, and possibly even a recording of the Russian version on YouTube.

Or, of course, you could simply ask the karaoke to play Mary Hopkins' "The Tavern", and then sing "Дорогой Длинною"!