Waait, Spelunky, right? I just took a look at La Mulana and it doesn't seem to have much in a way of varied landscapes like Spelunky and Terraria have, so with the shareware early Spelunky version/demo I've tried, I bet it's Spelunky! :) Since La Mulana is more about surviving and having hardcore enemies rather than getting various valuables.
Green_Hilltop: Uhhh...the only things that come to mind are La Mulana, Spelunky and Terraria. Terraria doesn't have mammoths, Spelunky I think didn't either (but has the bats, snakes and spiders!) so I guess it might be La Mulana? It's not anywhere on the bestselling page right now though, at least not in the top 40 or so.
Otherwise Heroes of Might and Magic 4 and later games would fit with the lush underworld, but they don't have Sub-Zero mammoths. Not to mention the other types of enemies.
(Journey to the Center of Earth, anyone? ;))
Ghorpm: Heh, heh, actually it is Spelunky! And it does have friggin'
Mammoths and they do shoot ice blasts and really get on my nerves :) Anyway - it's your turn
Ahaha, you were faster! :)
I tried the demo version and it's pretty fun, but not my type of game - I prefer normal platformers like JJ, I don't like roguelikes where you endlessly respawn and don't have much of an objective, like story points and so on. But in its exection it seems like a fun game.
Anyway, here's my next game -
Haha, it's so funny when the guards are jumping up and down like that because they stepped into the pit with hot coals! Fortunately I can jump just over them while they just run into/over them when they see me, haha! :D
(looks like GOG automatically merged both of my posts after I saw your answer and posted mine :)