I got a whole mess of perler beads that I am planing on making video game sprites out of (similar to these), but I forgot to get the oh-so special ironing paper. Can I use wax or parchment paper? Cause I have lots of those.
I use kitchen parchment paper all the time on the kids projects - works better than the stuff that comes with the beads.
Careful, there’s a few viruses in that link. 
Hijack: What is that little wizard-looking dude in the bottom right corner of the OP photo?
I assume you mean the little guy in the blue robe? He’s the Black Mage from Final Fantasy I.
Top row: Tetris pieces
Second row: Ghosts from Super Mario World, blue, red, and yellow viruses from Dr. Mario, Mega Man and Dr. Wiley from any of the NES Mega Man games
Third row: Ms. Pac-Man and ghosts, a poisonous mushroom from I-know-not-what Mario game, 1-up and super mushrooms from (I think) Super Mario Bros. III, a Pokeball from Pokemon, and (I presume) a Yoshi egg from Super Mario World
Fourth row: (don’t know the first three), Mario (with raccoon leaf), goomba, mystery block, and koopa from Super Mario Bros. III, the racer from Motocross Madness
Fifth row: (don’t know the first three), Fighter, Red Mage, White Mage, and Black Mage from Final Fantasy I
Bottom row: (don’t know the first three), a Metroid, and Samus Aran from I-know-not-what Metroid game.
Poisonous mushroom is from Lost Levels (on Super Mario All-Stars for SNES); the green and red mushrooms also appear to be the sprites from Mario All-Stars.
First three on the fourth row are Kid Icarus, I think. The goomba on that row looks to me like he’s from the original Super Mario Bros., but since the Mario to his left is clearly from SMB3, perhaps all four of those sprites are, as you say. As for the last sprite on that row, I would think you mean Excitebike instead of Motocross Madness.
Fifth row first two are from Legend of Zelda: Link to the Past.
The second one in the fourth row is Icarus from Kid Icarus, and I think the biker is from Excitebike, not Motocross Madness.
In the fifth row, the first two are a Cuckoo and a Big key from The Legend of Zelda: A Link to the Past for the SNES. The little ship is from…umm…some kind of side-scrolling shooting game.
The first three on the bottom row are from Burger Time.
ETA: Exactly what the guy up there said.
You know, this would make a GREAT set of Xmas tree decorations for a video game store!
This is also what we use at the kindergarten where I work. We regard fusible beads and parchment paper as consumables…
I’d stick with the heat-proof parchment, though. I don’t think the iron gets hot enough to start a fire with the regular stuff, but I’d hate to find out the hard way!
Reaper, Pit (aka Kid Icarus), and Monoeye, to be precise, all definitely from Kid Icarus. God, I played the crap outta that game.
The spaceship is from Galaga
Kitchen parchment is heat proof. If it can stand 40 minutes in a 425 oven, I don’t think 30 seconds with an iron will bother it.
Ah. Then it’s different here, as we have two types: one that is for baking, and can stand X minutes in a hot oven; and one that is for wrapping food, and makes no claims at all about heat resistance. The baking stuff is more expensive, obviously, but it’s the stuff you want for ironing fusible beads.
Well, I didn’t need to resort to parchment paper anyway. There was a piece of the “ironing paper” hidden inside the box of beads and the peg board I got.
I already made Mega Man, the “magic key,” and an Octorock from The Legend of Zelda.
The thick, non-porous white paper for wrapping food is called “butcher paper” in the USA.