A* Pathfinding For Large Distances

I have a situation where I am using the A* pathfinding method to move a creature across a tile based world.
This particular world can be extremely large and has many obstacles obstructing a creature’s path (trees in this case).
When calculating paths over semi-short distances there is not a problem. However, there are huge freezes which take
place when I try to calculate a path over three hundred tiles away (or so). And yes this is because I haven’t multi threaded
pathfinding yet, but I feel it would still be too slow even after threading it.

Anyways, here’s a picture to give you a sense of the scale.

That isn’t even the whole world, the minimap only shows 200 x 200 tiles whereas the full world may be infinite in size depending on the world generation rules.

I have heard that certain games, such as dwarf fortress I think? Split up their worlds into regions and somehow use those regions to improve the performance
of the pathfinding. Conveniently, I already have every world split up into 16 x 16 chunks which are currently acting as a method to define biomes, but I’m thinking
I can also use them for the purpose of quicker pathfinding.

I am not sure how this mechanically works. I am thinking the way this functions is that a path from the center of each region to all adjacent regions is calculated
and then cached, but I’m not sure. Not to mention that would significantly decrease shortest path accuracy.

So how can I use world regions to help improve long distance pathfinding? Or if there’s a better way in general, please let me know :).

Edit
I now realize this probably belongs in the artificial intelligence section.