Western Canada would be settled quite a bit earlier, and there'd likely be a province of *Deseret that joins the Confederation around the same time as Manitoba.
Would it? Both didn't happen in the US. Utah's population is larger than it would probably have been without Mormons, but the real population boom started there a couple decades after the Mormon pioneers arrived, at the same time as it did in Colorado and Wyoming.
Also, Deseret didn't join the Union, right? Utah did. That's because the Mormons raided other settlers, practiced polygamy, practiced slavery, and in general did things that caused the US government to feel obliged to make order through force. The Mormons practiced polygamy and slavery by the time they left Missouri (the picked up the latter practice there after being originally abolitionist), and there's no reason to think that the same desire to acquire children without pesky Gentile parents might not lead to raiding in the Prairies, even if there are perhaps fewer folks to prey on.
The Canadian government may be less able or willing to act to enforce their sovereignty on the region, but I bet they'd be pretty quick, especially since the fact that the Mormons are originally Americans means that Canada might fear the US will try to annex the region a la Texas.
Probably you end up with something similar to OTL, but with Mormons in Saskatchewan or whatever instead of along the Great Salt Lake or something like that. The region will be dominated by but not solely inhabited by Mormons, who will remain a somewhat distinctive culture while definitely being Canadian. OTL, Mormons recruited heavily in England; maybe the fact that they're now in the Empire instead of the US might make them a bit more attractive?
For what it's worth, Utah probably remains a generic Mountain West state, notable for the Great Salt Lake and Zion National Park (which obviously won't have that name)

. Possibly the Utah Territory doesn't get divided, though it would end up being very large if not - a little larger than California by area, and in the absence of Mormons and Las Vegas butterflied away, it might end up with not very many folks. It's warmer but dryer than Montana, though it does have decent mineral wealth. Nevada gold rushes might still end up leading to that half being split off, though, I guess.