2D side-scrolling game, had intricate level designs ranging from underground caverns to plains. You could ride animals (ostriches, if my memory serves me right), there were whistle-shaped thingies in the wall that would reduce the character size when you pass through them, which would enable you to walk under low surfaces. During (or at the end of) every level your character would go to a magician/sorcerer where you'd see a clone of your character, evolving after every level progression. There were huge clockwork bosses and whatnot.

I used to play it back in childhood on the NES but can't remember the name. It might as well be a SNES game. I'd be utterly glad if anyone could identify it.

Sounds like,

Adventure Island 1-4 AKA Monsterland AKA WonderBoy
Super Mario Brothers 2: Mario Madness
Super Adventure Island series on the SNES
Dino City.

If one of those are your answer, then vote RegalSin

No, it isn't. Sorry ):

Little Nemo: The Dream Master?