Types of Shoes/Boots in a Medieval Fantasy Desert Culture

In deserts with snakes and scorpions, ankle covering boots are common (although often sandals or bare feet are in use as well.)
In deserts where there are sharp stones, and/or hot sand temperatures, sandals are the least, boots not unheard of.

When your riders (horse, camel, whatever) use metal stirrups, like the ones in use by most riding horses on our world, boots with heels and hard soles are the most wanted footwear. But other kinds of footwear have been used.

But in history, many peoples, spread all over the world, have ridden animals without stirrups or with a different kind of stirrup which does not have the same needs for boots, or even any kind of footwear.

People who walk bare feet all the time have though skin on the soles of their feet. So if you are inclined against boots, you can have your peoples go bare foot.
On the other hand, you are the writer, if you want your people to wear beautiful boots, by all means have them wear those.

Typically, before rubber became the norm for soles, boots were made out of leather and some sort of yarn made of animal hair or plant fiber. In the making of boots often wood was used to make a last (the form of the foot to build the boot around) but you can invent something else if there is no wood in your world. Some boots will have been made out of wood as well as leather, but it is not needed.
With riding animals you will have leather (from old/butchered riding animals or from other animals used for food.) And adult animals have thick leather, it 'just' has to be tanned in such a way that the thick parts get strong and sturdy.

Dress shoes (at least in the 20'th century) were soled with leather, and walking on streets their soles could last a year or even longer, then you would take them to the cobbler and you would get them re-soled, which would last an other year or two, depending on the use.
Riding boots will not wear as much on most of the soles, though leather should do for them for a year at least, so you may need to 'invent' an easily replaced part where the stirrup damages the sole, or you can just have the readers assume that the whole of the sole will be replaced if needed. (Or leave it out, you will also not describe how often they replace their riding trousers, unless it is vital for the story.)

You can go into the design and making of the boot or leave that out, as fits the story.
But history on earth on earth will have much information.

Go back at least to the pioneers in the USA and those natives who used horses, or the same time or before in Europe and Asia, for samples that would fit in your time/tech frame.