How strong/consistent is the coverage of various parts of Mongolia by the different satellite navigation systems like GPS/GLONASS?
Same as anywhere else in the world, in terms of the space-based GPS system and receiving the signals from those satellites.
The main difference would be with A-GPS (assisted GPS) which can use wifi networks or cell towers to accelerate the location determination algorithm. The lack of these in the Mongolian desert would presumably slow you down a bit, however as long as you can pick up a few of the satellites' signals, you'll get it.
Source: I've been to Mongolia and used GPS on my old smartphone.
GLONASS system provides a real-time map of integral availability for the current day. Availability is measured as the percentage of the time during the day when you could get a reasonably precise fix in an open area. It used to be important a few years ago when the coverage was less good. This is how it looks today:
As you can see, there's 100% coverage over Mongolia and 99.8% coverage globally. As a reference, this is how GLONASS coverage looked in 2010.
GPS currently provides 100% coverage everywhere, every day, so they don't publish coverage maps. Instead, they publish the DOP (Dilution of Precision) maps which help to estimate how precise a fix will be. Essentially, this is a factor by which you have to multiply the estimated error due to poor satellites location (error is bigger when satellites are concentrated in one region of the sky, and gets smaller when they are spread out evenly).
As you can see on the current map, the PDOP (position DOP) factor is 1 almost everywhere including Mongolia, so you can expect nominal GPS precision there. In a few places the PDOP factor is 2, so the position error can be twice as large there.
If your GPSS receiver combines GPS and GLONASS, then you're practically guaranteed to get 100% coverage with DOP factor less than 1 everywhere at any time, assuming you have unobstructed sky view (which should not be a problem in Mongolia).