The word is Shoshoni or Ute (I can't remember which right now) and I think means "crane" (the bird), but it's been a few years since I used it, so my memory may not be perfect. If you can find a copy of "Native American Placenames of the US" you can find it there. I'm not at home right now and can't look it up. If you want to wait a few hours, I'll revise my entry here to be accurate.
Stories like the "frozen penis" story are called "Folk Etymologies". They are created because the person doesn't know the true history of the word and makes something up that sounds like it. A classic example in English is "butterfly", which many people say is a metathesized form of "flutterby" or because their wings are yellow. They are guesses by people who don't know where the word really comes from. The Shivwits did not live anywhere near the Wasatch, so the word of a Shivwits Paiute is definitely folk etymology.
EDIT: I just talked to my buddy at Brigham Young University (I'm at Utah State University). He's the leading authority on the Shoshoni language (I specialize in the whole group of languages that includes Shoshoni and Ute). There just is NO good etymology for Wasatch because it has been in use for so long. "Crane" works, but it doesn't make much sense. Actually, we're thinking that the first syllable is related to wa'a- 'cedar'. That is a much more likely etymology. The last consonant is from -ttsi which is a common noun suffix. The -sa- in the middle is still unidentified. Whatever it is, I can guarantee that the "frozen penis" and "mountain pass" etymologies are incorrect.
EDIT: The word is Shoshoni and means "blue heron". The mountains were named after a prominent Shoshoni leader of the 19th century. This may also be a folk etymology, but it's what I wrote in the book "Native American Placenames of the US". "Mountain pass" is wia- in these languages.
I was the editor for the "Native American Placenames of the US" for placenames in Utah and the rest of the Great Basin.