According to what I read about Russian railroad troops, their operations could be divided in two parts - before the pre-war border and after.
Inside the old Soviet border there were the roads re-gauged by Germans. But those needed no "re-re-gauging" - due to the extensive usage of railroad destroyers by German troops Russian railroad workers were thinking not in terms of re-gauging, but in terms of rebuilding.
A photo of a German railroad destroyer at work and the results:
And another one:
And when there was no time for one of those (they worked at around 7 to 10 kmph), Germans just used explosives.
After the Russian offensive outpaced the ability of German troops' to destroy the usable track behind them (they mostly stuck with destroying the bridges and tunnels), Russian railwaymen did start re-gauging European track to Soviet standard, but this differed by the rolling stock they had on hand - sometimes the roads were restored to European standard so the captured trains could run on them, and then re-gauged again when Soviet-gauge rolling stock arrived.
According to the site of main Russian railroad operator, during the war Russian railroad troops rebuilt ~120000 km of railroad track.
Sources (Russian language, mostly):
1) Кабанов П. А. Стальные перегоны. — М.: Воениздат, 1973