Well, and this is purely guessing, I'd think it's because every hallway square will also have access to the tile directly above and below it. I'm not entirely sure how pathfinding works but if it looks at which tiles are accessible, than that might add up.
Well, there's that of course. But wouldn't that pretty much mean that every single tile you carve out, anywhere on the map, would contribute to this?
Yeah so I'm not sure how big a deal it would actually be. Basically, in an open area, an open space will have access to 8 other open spaces, and a staircase will have access to 10, since I don't think they can go to tiles adjacent to the one above them. If they can... then it's something like 26, and that might be a problem, but I really don't think it's the case.
I should really point out that again that I'm just guessing, and hoping that somebody will know enough to correct me if I'm wrong, and/or get the idea to try and test what actual effect it has on fps. All I know for sure is that the biggest drain on FPS is probably pathfinding, and that I've heard up/down stairs are worse than ramps for pathfinding.
Just occurred to me, I actually think staircases might have access to adjacent tiles on the levels they connect to as well. I can't remember atm if I've seen them move from a lower/higher z-level straight into an adjacent tile without walking on the staircase of the current z-level first, but I've seen several times when I've had 4x4 staircases where they've moved both down one z-level and sideways to another stair in the same tick.
Still though, I guess it's all moot if we've no idea how pathfinding actually works. I'd also assume there's two pathfinding algorithms, one for short distances which is called every tick (i.e. to find out if there's another dwarf blocking the way and whatnot) and another for long distances which sets up the route the dwarf will take and which is likely called fewer times; possibly only when a new order is triggered.