The reference to Russia is not unexpected. Lithuania was occupied by Russia from 1795 to 1918 so there was no country called Lithuania during that period of time.
However, on many ship registers, the birth country was listed as Russia but for ethnicity they recorded Lithuanian.
Do you have copies of the actual church marriage register. Sometimes the priest would record the place where the pride and groom were baptized in Lithuania.
What port did he emigrate from?