I get that they had the Trans-Siberian railroad, but they'd need coal/diesel to run the trains, and food and water to sustain millions of troops while they traveled, and ammunition and vehicles and fuel for the supply line. All that in areas of very low populations and no economies of scale.
All that in areas of very low populations and no economies of scale.
You underestimate the economic importance of the Trans-Siberian railroad itself. SG Marks has a pretty good book on the economic impact of the railway in Siberia called "Road to Power". The railroad was constructed in late 1900s and it had an immense effect on Russia almost immediately. Firstly, the eastern fringes of the Russia had an important agricultural base. Upon completion they were able to export around 500 000 tons of grain annually. Compared to Ukraine (the breadbasket of Russia), that produced 2-4 million tons of grain annually, that's a pretty good slice of the Russian food market. The rest of Siberia was rich with minerals, wood and coal. And of course you had a big chunk of the population doing all kinds of jobs all year round. Fishing and farming during the summer and spring, fur trapping, hunting and working the mines during the autumn and winter.
When the railroad was constructed it opened up the road for many industries to establish themselves and existing industries to expand. From 1906 to 1917 about 5 million people migrated from European Russian Empire to Siberia. In the few years after the revolution up to 1930s, those numbers soared to 6-9 million people who either got resettled by the state or willingly migrated. So, you had a very important growth in Siberia that was fascilitated by the Railway. As a result, all along the line new settlements started popping up. And since it proved to be such a vital route, not only for Russia, but also for the rest of Europe (since it connected China and Japan with the European markets), its maintenance and supply became one of the most important priorities for the local economies.
Also, it was of extreme strategic importance. During the Russo-Japanese war, the Revolution, the Civil War and the Interventionist invasions, it became the main front on which the war in Siberia was waged. Whoever controlled the railway controlled Siberia. So you had armored trains going back and forth, with soldiers living long-term in the trains themselves. Because of this, many more resupply points were established.
So by the time Germany declared on Russia, there was already a pretty important infrastructure set up for the supply of the lines. The Siberian economy was booming, and urban centers (especially close to the Pacific) started competing their western counterparts in size and wealth.
In the first 6 months of the war the Soviets managed to relocate their whole industrial base from European USSR to the Urals and Western Siberia. So you had that going on, further supporting the line.
Fuel was very hard to run out of, because even if you ran out, you had a train full of soldiers you could order to go out and chop down wood for fuel. And there were regular resupply stations all along the line.
Also, this was the main way by which American lend-lease aid reached the Soviet Union. The Atlantic was infested with the Germans. But in the Pacific, despite the Japanese having a war with the US, they still feared the USSR and didn't want to open a second front as Hitler eagerly did. There was an uneasy and unofficial ceasefire between Japan and the USSR during WW2. So they refrained from attacking freight ships with the Soviet flag, which were able to sail to the US, Canada and Latin America and bring back precious supplies, most importantly food. This was then transported through the railway all the way to the front with Germany. To understand the bulks we are talking here, the Trans-Siberian Railway transported more tonnes of supplies than the other two main routes by which the Allies supplied the Soviet Union (Iranian corridor and North Atlantic route).