Anecdote: I learned BASIC in 1981, and one of my first programs generated mazes. I tested it a couple times on smaller grids, then submitted a job to fill an entire sheet of green bar paper. Next morning, I asked the operator for my printout, and got chewed out because they killed my job after it had consumed some insane amount of core time.

That was my first lesson in complexity. My program was something like O(N^3) or worse.

But I've read that good crossword puzzles are as much of a literary exercise as a computational one.

You might enjoy this: https://www.jamisbuck.org/mazes/. The section headers link to his (IMO really excellent) articles about maze generation algorithms, plus there’s a more comprehensive book you can buy.

(I doubt kid’s mazes are made using these precise algorithms, but either way they’re interesting!)

One way could be to plan the main route first and then generate other routes.