In most of the newer Mario video games Mario can do a "wall jump." This is when a person bounces back and forth off of two vertical parallel walls, moving upwards with every bounce. Is this humanly possible?

Yep.

Not as easily as in the game (a short, plump plumber might have a tough time of it), but I don't see any reason it couldn't be done.

I’m pretty sure I’ve seen parkours/free-runners do this.