I rode from Chita to the Black Sea last summer, used a road atlas picked up at a gas station in Russia. Not clear if you can read Russian? If so, you shouldn't have a hard time finding adequate road atlases once you land in Vladi.

Also, not clear how detailed you mean...there are very detailed road atlases of each region in Russia, but since you'll be crossing about fifty regions (OK, maybe fewer) not sure if it makes sense to lug all of them around. Actually from Vladi to the Urals you don't need a very detailed map, as there is basically only one road (with some others branching off here and there). Once you get into the Urals the road network opens up--at that point I would try to stay off the main roads, cuz there is less traffic and fewer police (and its just nicer riding through the countryside).

As far as GPS--I used a garmin zumo but didnt' have any maps for it--basically used it as a compass and for dead-reckoning to hotel lat/longs. There are maps for Russia in a set called "Roads of Russia", now up to Version 5.12 I think. I believe that about many of the regions in this set (maybe 30?) are routable, the others are not. The problem is that to run these maps you have to "russify" your gps, which involves changing the firmware. I would check the zumo forums for more info.