Есть желание в мае проехать через Монголию на Алтай.

Южная трасса асфальт от и до. Можно из Батора заскочить в Хархорин, оттуда спуститься вниз на южную, и идти на запад. Неплохо сделать с трассы отворот на Хонгорын Элс, потом снова вернуться и идти дальше на выход. Недалеко от границы очень красиво в Ховде и перевал с озёрами из Ховда до Улгия. Ну а потом Алтай.

В одну каску?

Как по мне, так гораздо красивее по Северной трассе от УБ на Цецерлэг, до Улангома, а там два варианта, он Наранбулага на Ховд и далее Баян Ульгий или сразу через горы на Баян Ульгий под Ачитом, но это на любителя, Ховд предпочтительнее, а в Гоби заскочить сразу под УБ.

Рекомендации сильно (даже принципиально) зависят от того - сколько у вас времени на Монголию.

Почему вы хотите заехать через Верхний Ульхун? Через Кяхту гораздо удобнее и быстрее, даже если вы едете из Якутии или других мест Дальнего Востока.

Если заезжать на пески Хонгорын Элс - надо не возвращаться обратно до Улан-Батора, а через Сэврэй и Гурвантэс заехать в каньон Хэрмэн Цав, от него на север через Шинэжинст до г.Алтай (по дороге несколько интереснейших мест), от него через Улиастай на Воронку, Арку, южные и северные дюны озера Улаагчны Хар нуур, от северных дюн на вашей машине (очень интересная, но сложная дорога через приличные перевалы и несколько тяжёлых песчаных засад длиной в километр) можно проехать к северной трассе до Сонгино, оттуда по асфальту мимо озера Хяргас нуур (интересно только если вы рыбак, в другом случае делать на нём нечего), потом через Наранбулаг грунтовка до Ховда, от него по асфальту до Ташанты, ну и далее всякие интересности Горного Алтая, с обязательным посещением Марса 1 и 2, доезда до альплагеря Актру, разумеется долина Чулышмана через пер. Кату-Ярык, с посещением водопада Куркуре, Учар и ночевкой на косе Кырсай (южный берег Телецкого озера). При наличии времени - Красные озёра в районе Усть-Коксы, и Мультинские озёра чуть дальше.