First, I added a for loop that randomly removes a random amount of walls (between 25 and 30 seems to be perfect). This didn't help much with speed, but it definitely made the maze more fun to run around. Before this change, it was really just one long corridor with the occasional small branch. Now, it's a whole sprawling complex of hallways, junctions, and dead-ends. Awesome.
I also changed how I was storing and handling CornerWalls. On a hunch, I guessed that what was really slowing the generation down was how every CornerWall stored a sprite for every kind of corner wall that could be made. I fixed this by splitting the CornerWall's fifteen sprites into fifteen Corner# entities, each with just one sprite. It sped up immediately! Good thing the other walls (HorizWall and VertWall) only need one frame.
Should I upload a demo so everyone can run around the mazes themselves? It's pretty nifty. ;)