There is a very detailed list of Mongolian customs at Mongolian Ways (interesting reading). Amongst numerous snippets of information and advice is:
Mongolians touch each other more than Anglo-Saxons do. It is normal to see men or women holding hands or putting their arms around each other's shoulders. Mongolians tend to touch one another, even those whom they do not know.
So I very much doubt offering to shake hands with man or woman would be taken badly. The list is introduced with:
Mongolians are very tolerant people and most will not take offence when a foreigner is unfamiliar with local customs. It is not possible or even expected of you to know all the customs of the Mongols in the course of a short trip.
So it seems even what might be a social faux pas in Mongolian culture would be forgiven from a foreigner anyway.
However, there is also mention that "Mongolians are always happy and appreciative when a foreign visitor takes the time to learn some of their customs and shows this during greetings or visits." so it may be worth bearing in mind that the Mongolian custom when greeting strangers is, informally as may be more relevant for you, :
a nod and a smile, with the greeting , "Sain bain uu?" (Are you well?') usually suffices. The expected response is “sain” (well), even if you are not feeling your best that day.
or if formal ("during Tsagaan Sar"):
roll down your sleeves and extend both arms. The younger person should support the elder person’s arms below the elbow. The older person will ask “a-mar bain noo?” (how have you been?) and the younger responds “a-mar bain aa” (well). If a khatag is being offered, fold it lengthwise and hold each end in your extended hands as you give the greeting, then place the khatag into the person’s hands afterwards. Mongolians greeting one another rarely kiss each other on the cheek. An older person will often grasp the head of a one younger during the greeting and smell their hair or face.
Note that neither includes a handshake.