"Yekhali" is Russian for "they are leaving / traveling out [of town]," generally understood as being by wheeled transport, not by foot.
"Tsigane" is Russian for "gypsies."

So, from po-Rooski to po-Angliiski, the phrase translates: "The gypsies are leaving [town or place for some other place]." Heavy atmosphere of departure, sadness perhaps.

Sadly my copy of Bikel's LP, bought 2nd hand, lacks its booklet, which transliterates the Russian words, if anyone can find a copy and then work backward through the Cyrillic.

Nor is my Russian isn't good enough to understand singing in that language, particularly Bikel's, which is notoriously ba-a-a-a-a-ad. All honor to Theo but he fudges a lot, and now and then lets gibberish take the place of any Russian he hasn't got, which seems to be a lot. At best it (like that of the notoriously inaccurate Ivan Rebroff) is broken Russian---that's not my conclusion but that of a friend who is a native Russian speaker.