This is a fascinating question, but I am afraid any answer must be rather conjectural. Siberia is big--alone, the region is larger than the United States, and represents nearly 80% of Russia's area (and sparse: Siberia has less than 25% of Russia's population). The katorga system of prison labor emerged under Alexei Mikhailovich, but became much more prominent in the mid-19th century under Nicholas I, a reactionary ruler whose inauguration was marred by the Decembrist Revolt. Starting near the end of his rule exile sentences became even more common in response to the increased importation of Western philosophy during the 1840s, and in turn increased agitation for liberalization (amongst other political backdrops, including the revolutions of 1848). This is probably a little earlier than the time you are looking at, but prison labor remained common throughout the 19th century.

Much scholarly focus is on intellectuals imprisoned for their writings and even readings, as was the case of Fyodor Dostoevsky, who was imprisoned at Omsk from 1849 to 1854 for possessing Belinsky's Letter to Gogol; nonetheless, katorga camps, as well as gulags, had plenty of petty and violent criminals.

Murderers were subject to capital punishment and execution in the mid-19th century, but hard labor was a more common punishment; as we see with the Decembrists, only five would-be revolutionaries were executed, and the rest exiled to Siberia. These punishments were generally on the order of one to two decades, and involved hard labor, meager rations, and squalid living conditions. Dostoevsky's Notes from the Dead House is a fictionalized memoir of his imprisonment, where the narrator has been imprisoned for ten years for the murder of his wife. The vignettes we see are at times sympathetic to the general populace (the narrator, like Dostoevsky, was an aristocrat; nearly all other characters we meet are criminal peasants), but overall evinces the indurate nature of the prisoners, guards, and environment.

There were katorga camps distributed throughout Siberia, which makes pinning a plausible one down difficult. The camp that Dostoevsky was sent to, Omsk, is on the Irtysh River in passable terrain, but wouldn't send our runaway through China; instead, they would have to walk though Kazakhstan, on the margins of the Russian Empire (Omsk is more-or-less due north of Bukhara, however).

Other prominent camps included Chita, Kara, and Nerchinsk. Chita is on the Ingoda and Shilka rivers, which heading east and then south to the Onon River would get you pretty close to China; Kara was part of the Nerchinsk system, but was disbanded following the suicide of revolutionary Nadezhda Sigida in 1889, and by the 1890s the tsarist government abolished the use of corporal punishment on nobility.

Nerchinsk is east of Chita on the Shilka River, which would place us closer yet to China. All of the rivers are frozen in winter to spring, and the average high does not crack freezing from November to March. Further west there were camps in Irkutsk and on the Yenisei River. These are north of present-day Mongolia, and would provide an easier route to Bukhara, while the camps extended eastward to Sakhalin.

Any of these would be a possibility, but I would guess (and, of course, just a guess) that either Nerchinsk or the Yenisei Basin present the easiest avenues for the path of a runaway you have outlined. Further north or east you would end up in more difficult terrain further away from the border.

As for the plausibility of runaways, there was no shortage of prisoners who sought to escape the katorga. Pyotr Kropotkin, in Russian and French Prisons, surmises that more than twenty thousand runaways had fled; the harsh environment was deterrent enough, and Kropotkin proposes that a greater number die than live. He provides a rather curious anecdote of villagers leaving food out for the runaways in their windows, which provides an interesting image in the relationship between the prison camps and the rural villages.

Varlaam Shalamov's Kolyma Tales, set in the Magadan Gulag, offer a Stalin-era view on the ease of fleeing in "Major Pugachov's Last Battle":

The taiga was cold and stern, and the enormous twisted pines stood far from each other. The forest was filled with the anxious silence familiar to all hunters. This time Pugachov was not the hunter, but a tracked beast, and the forest silence was thrice dangerous.

It was his first night of liberty, and the first night after long months and years of torment...They were free, but this was only the beginning of the struggle, the game of life.

They agreed it would be better to die than be a convict, better to die with a gun in hand than be exhausted by hunger, rifle butts, and the boots of the guards.

https://www.reddit.com/user/Taylan_K/comments/sh9ppf/great_grandfather_text/?utm_source=share&utm_medium=web2x&context=3

I uploaded a photo of the text, it's not complete as some info also came from my grandma but that's what I know about his journey. The thing is that this man (Haciapul) is actually the father of my great grandfather. Funny thing is, my great grandfather (Halit) also landed in a Gulag. I guess the men in my family just liked to mess around with Russia. If anyone wants to know where Halit was imprisoned I can post this too!