I was in UB two years ago, the only bikes I saw for sale were the primitive 2-stroke Izh (if you watched Long Way Round, they bought one of those for their cameraman after his BMW lost its brakes). Light, simple but not very reliable, that's what I gather.
But as I've said, I did not look around for western bike dealers - it may be worth to do at least an internet search. I saw a bunch of Europeans on rented KTM's near UB. Maybe the rental company would be willing to part with one of their bikes?
Novosibirsk in Russia has a large inventory of used bikes, mainly japanese. you would be starting quite close to Mongolia (by russian standards).
let us know what you came up with!