Knowing the size of the floor doesn't really matter, unless it's so small you can guarantee that starting in the center will still make sure you have enough room. In which case, start in the center!
What really matters is how big it is. Some games, like the Bard's Tale series, had spells like Scry Site which showed you your grid coordinates. Absent something like that which gives you your current position, if you're going with physical paper, you don't have much option other than to notate when you hit the edge of the paper and continue on a new sheet.
I would typically do that by leaving the outer-edge lines of squares on the piece of graph paper empty so that I could put notes about where they joined up with other sheets. So if I'm mapping level 1 of the sewers and have a hallway running right off the side of a piece of paper, I might notate on the last grid square "S1-A" to denote that it is "Sewers level 1 exit a" and then on my new sheet of paper, I'd put an entry point on the left side and name it "S1-A" so I'd know where it joins up.
Later, you can redraw your maps with your newfound knowledge of their overall size, or you can just lay the different pieces of paper next to each other. You can even get fancy with scissors and tape if you want.
That said, short of a game like Bard's Tale that gives you the tools to make mapping a little easier (where all maps were 22x22, and they gave you a spell to figure out your position), I'd go with a digital option like originaluser suggested in the comments if you're intent on discovering and mapping everything
Given that most of these old games probably have maps on the Internet at this point, a good compromise might be to pull up the map when you get to a new area, find your starting position, figure out where it is relative to the whole map size, and then start your own map there. Sure, you're cheating a little by looking at the online map, but if you're not starting at the map too hard you probably won't have much given away other than which corner of the dungeon you're starting in, which is the very piece of information you were hoping to obtain.