I apologize in advance if this is already answered somewhere, but I can't seem to use the right search query to find what I'm looking for.

Since I like to draw a very rough plan of areas in games that are set up to be a labyrinth or just complex in nature on a piece of paper to orient myself quickly and effectively, I would like to improve doing that by hopefully learning some techniques and rules of thumb from you guys.
My maps usually just support my memory. The maps become almost unreadable without having the picture I have in my mind, so others can hardly ever make use of them. Even I can hardly read them if I look at them weeks later.

So for me aesthetics are less important, but readability is.

The problem I often have is underestimating the size of a region. So I often start reducing the proportions when I get to the "end of the paper", which makes it even more unreadable for others.
I thought about using software instead so I can just keep extending the paper as far as I want.

I can use Paint or Photoshop, but I despise Gimp.

Pretend you would walk though multiple levels of a complex mall, when you get home you want to sketch it in 30 minutes from memory with all shops on it. So someone else can take your map as a guide to instantly find a certain shop. Or draw the map as your traverse through the mall.

How would you do that? How much detail do you think is needed?