I was listening to Louis Armstrong's "Dark Eyes" many years ago too. He seems to have improvised lyrics. His recording is HERE [wav file; 07:21].

The original poem (whose title seems to have been "Chernye Ochi") was written by Evgenii Grebenka (1812-48) in 1843 (Click here for romanized text; click here for Cyrillic text).

According to James J. Fuld (The Book of World-Famous Music, 4th ed., pp. 417-418), the first known printing of "Otchi Tchorniya" as a song was shortly after March 7, 1884, though no copy of it has been found (it was republished before 1897 by A. Gutheil, Moscow). The reprint is in Gutheil's Favorite Songs of Moscow Gypsies (in Russian), with this note: "a Gypsy Romance to the melody of the 'Hommage-Valse' by Hermann."

Transliterated titles I have found include "Ochi Chernye"; "Ochi Chornia"; "Otchi Tchorniya"; "Otchi Tchornie"; "Otchi Tchornia"; "Otchi Chornia"; "Ochie Chornie"; and "Ochy Chornia". Feodor Shaliapin populairzed this song (listen to him HERE). The Russian Red Army Choir version is HERE [zipped wav file] and HERE [lyrics]. Vladimir Vysotsky's version of "Ochi Chernye (Narodnaya)" [RealSlideshow] is interesting (Click here).

~Masato