I use my 19"x24" chessex battlemat for combat encounters.
I use a regular sized 8.5"x11" sheet of printer paper for the dungeon map.
I draw out the shape of the dungeon, not the details, just as some adventurer who is mapping it would do, for the purposes of not getting lost and showing where all the rooms/corridors go to. This means lines for corridors, small boxes for rooms.
I'll often hand out this sheet to the players as a prop they find early in the session. They'll then put a small token on it to show the party's current position.
When combat happens, we hop over to the batttlemat to draw out the immediate area.
This works pretty well, and for the most part, doesn't take much time to deal with.