I've seen something similar to this proposed before, but not with much detail.

The basic idea is to break down the map into smaller pieces, so that pathfinding from one location to another becomes much simpler, because it only has to look at the connections between large chunks of the map, rather than considering every tile.

Filling out the map with these could be done by a relatively simple method to initialize thing with, which can be modified after as the world is altered:

1. Pick a random unincorporated tile with a floor under it.
2. Expand a square out from the tile until you hit an obstacle or the border of another rectangle.
3. Expand out in the remaining directions until you hit another obstacle or rectangle border, keeping the area rectangular as you do so.
4. Repeat from #1 until map is covered.

Then you store connections between each rectangle to the rectangles adjacent to it, and when you need to pathfind, you can just do it from your starting rectangle to the rectangle the goal is in.  Which would be much faster than searching across every single tile.  You could store the borders as simply a range of tiles as well to save space.  Since these are rectangles, then they will only ever meet at a contiguous section of one of their faces.  A single rectangle could have multiple different rectangles along it's border, but never the same one at multiple places.  Rectangle A might have connections to B on the north face from 1-3, and from C on the north face from 5-7, but never B on the north face from 1-3 and 5-7.  Not to mention, a connection to a single rectangle could only ever be on a single face, all that's needed to be stored would be to provide a list of connections, and a single start and end tile for the range for each.  A dwarf could move to one of those tiles, and then just step into the next rectangle on it's path.

Being always open rectangles, free of obstacles, has other advantages as well, for example the distance of a path between two rectangles can be determined just by the manhattan distance, or something similar, like taking the greater of the distances of the x axis and the y axis, rather than the addition of them, if you want to treat diagonals as being the same length.  It only needs to look at the starting and ending coordinates, since the path between will always just be a straight line.  Pathfinding within these rectangles is also trivial, it's basically nothing but a straight line.  Say for example you enter at the west side of a rectangle, and want to leave by some point on the north end, you can always get there just by some combination of north, northeast, and east.  If you compare where the starting and ending points are, you can even always do it with just 2 possible directions to move in, although you might want 3 to be able to sidestep dwarves.  And at worst, you might need to look a square or two ahead to avoid running into another dwarf or such.  This also applies to any two points within a rectangle, all of them can be reached in a straight line.

Now, all of that could be fairly easily be done for a static map, but what happens when the map changes?  There are some possible resolutions to that:

If an obstacle is created in a rectangle:
1. If it is possible to shrink the size of the rectangle by 1 in one dimension or the other to remove the obstacle, then do so, preferring the side which leaves the fewest tiles unincorporated if it's at a corner.
2. If it's not possible to do the above, it can be broken into two smaller rectangles, with some tiles left out between them.

As for the unincorporated tiles created above, you could make them into 1 or 2 long rectangles in either of the above cases.  And filling in the information for the new rectangles should be easy, on one side, it's the parent rectangle, on one side, it's removed, and on all the other sides it's the same, although with the specified ranges for the edges reduced.  Although you would have to then go to each of those remaining connections and modify the connections accordingly

On the other hand, when an obstacle is removed, you could do the opposite:
1. If it is possible to expand an adjacent rectangle into the open tile, then do so.
2. If two rectangles completely share adjacent faces, then merge them to create a new rectangle.
3. Recheck #2 for the new merged rectangle.

Such that, any rectangle which has been broken by the previous method, would be reconnected if those obstacles are removed.  You might also want to have the merging step at the end of the first method also, but then the removal of obstacles doesn't always return things to normal, but that may be an acceptable tradeoff.  And merging is easy too, all you have to do is remove the connection data for the adjoining faces, combine the connection data, different connections just being both present, same connections having their ranges extended, and then make the necessary modifications to the connections of the rectangles it connects to.

On top of this, there are situations where there may be smaller rectangles left laying around, or where the initial rectangle building wasn't ideal.  Like say there's a tree along the faces of 4 rectangles, next to the corner, so that when it's removed, it leaves a 1x1 space, which would have to be it's own rectangle, since none of the others can expand.  Or if a new rectangle gets itself formed in a doorway and across a tiny section of hallway.  You could occasionally pick a random tile laying around, and attempt to generate a new rectangle from that point, ignoring present rectangles, but not obstacles.  If the new rectangle covers a larger area then all the rectangles it would destroy, then it could be created, and new ones made to fill the empty spaces.  Although I'm not sure how that would work in practice, it would lead to larger rectangles, but not necessarily fewer.

Other additions:

The above method only covers normal walkable tiles.  Once you've covered all the walkable tiles, you could then use the same sort of method to make rectangles/rectangular prisms, that consist entirely of open space, or entirely of water, or entirely of magma, etc.  The connections between these wouldn't need to be much, since they'd still only ever connect on a single face.  A piece of ground, open to the sky, and connecting to a single block above it, would only need to specify the connection, and it's starting and ending coordinates, which would just be opposite corners of the rectangle.  Even between two cubes, each would only need to specify the connection to the other, and the corner ends of the connecting face.  What's more, each area would have it's own specific movement type inherent to it.  All of the land tiles already have their rectangles set up, and connection to a rectangular prism of air would only have to be considered for flying creatures for example.  You could have connections marked by movement type, and only creatures that can move in that way would even consider that connection as a possibility.  And movement from an entrance or point within it to any of the connecting faces, or any other point within it, is still a trivial solution.

Stairs might benefit from being covered by rectangles separately as well, you could make a rectangular prism out of them, and then they would be the only land-based cells that would have to consider connections above and below them.  Not to mention you could then more easily exclude them as a movement type (like for caravans).  Ramps wouldn't really need them, since they replace a direction like east, with east-up or east-down, but never both at the same time.  In fact, you could have flat rectangles of land that ignored ramps, and just treated the side that's a level higher or lower as being on the same level, since that's largely how dwarves treat it, and it would still all work out the same.  Well, you might have some issues in the specification of connections to surrounding rectangles or cubes of air.

Things like water flowing out into a rectangle could act like an obstacle, splitting rectangles into smaller pieces, and then, if you don't do any merges on breaks, or if they don't get merged in the meantime by any optimizing process, then when the water dries, it should all merge back together into a single rectangle, most of the time at least, you could end up with some oddities if it dries from the inside first.  Maybe put damp tiles as higher priority to check for optimization.  You could also cover water on the ground as a separate set of rectangles for movement purposes, either group them with ocean rectangular prisms, or have their own water/walkable set.  But all of that could be a bit processor intensive whenever water flows across an area.

Another way would simply be to keep the rectangle intact, but put a marker on it or something, that there's a temporary obstacle like water or magma (or enemy units nearby?)  And then perhaps an A* search rather than just a trivial search could be done to see if the destination could be reached, or upon reaching the rectangle, the dwarf could check to see if it could get to it's destination on the other side of the rectangle, and if not, re-check for another path.  That might be less processor intensive then breaking it apart, at least for large amounts of water, or small numbers of dwarves attempting to cross.  Or the same sort of connection map or whatever exists currently, applied to rectangles like this that are of mixed movement types.

One issue that isn't covered is the current pathfinding cost user modifications.  In order to make that work, it would either have to only apply to whole rectangles, or make it so rectangles can only be formed along constant pathfinding costs, or the pathinding cost is averaged out over the whole rectangle, or have it ignore pathfinding costs, effectively removing them.  Otherwise, it would actually have to check the cost to cross each rectangle itself while it's looking for a path, which would be ugly.  #2 supplies all the added functionality of pathfinding costs, just with a somewhat reduced improvement, since it has to make more rectangles than normal, although not much if your pathfinding change fills a whole corridor or room.  All of the others reduce functionality in some way.

Overall:

This system should provide a large advantage to pathfinding, by significantly cutting down the number of nodes that have to be searched to reach a destination.  In fact, A* would only have to work on the higher level mapping of things, all the movement within rectangles could be handled trivially, by a system that doesn't even need to search.  And it should be able to produce the same results as far as pathfinding choices go, or quite close to them.

It does require a bit of memory for the mapping, pairs of coordinates for the corners of each rectangle, and pairs of coordinates and a pointer or index for each of it's connecting rectangles.  As well as perhaps some other useful information, like a consistent movement type for the whole rectangle, land, air, water, etc.  It could also get some of that memory back, by it's A* search being much shorter, and having to consider and store many fewer nodes, and each dwarf could just store a smaller set of coordinates for the path to their destinations, that they could trivially travel between in basically straight lines, while still allowing them to walk around other dwarves and such.

The adjusting, splitting, fusing, etc. of rectangles could take up a little bit of processor time, but that would only happen when a modification to the world is made.  And should be more than made up for by the greatly reduced time spent on pathfinding.  Especially since calculations relating to rectangles would be constant with the size of your fortress, taking the same amount of processor time no matter how many dwarves you had.