Thanks for all of the discussion. After reading it all and pondering for a bit, I present...
Proposed New Settlement System
Settlements no longer have an influence radius, instead they are associated with regions. When founding a new settlement you place a central administrative structure. That structure represents the "claim" to the region. When placing the structure, the target region will be highlighted both on the local map, and on the minimap. You cannot claim a region that is already claimed by another settlement (yours or otherwise).
At certain population thresholds a settlement can construct an additional administrative structure in an adjacent region. In the future settlements may be restructured to contain districts (mini settlements within a settlement), when/if that happens it will be based on regions (each region becomes a district).
Structures may only be placed in a claimed region, but citizens will be able to harvest trees, gather pigs, and build roads in claimed regions, as well as regions adjacent to claimed regions.
Ownership Changes
If an administrative structure is destroyed, then that region becomes unowned, any citizens will evacuate, and any structures will become useless. If another group places an administrative structure in that region they gain control over the structures and any items they contain, effectively capturing the settlement. This could potentially mean the capture of Maskling settlements, or Masklings capturing your settlements. Note that this excludes the people, they'll just flee to the remaining parts of the settlement.
If a settlement loses all of its administrative structures, and ceases to control any regions, then that settlement ceases to exist, and the population converts to immigrants. This allows you to abandon settlements by deconstructing the administrative structures.
Administrative Structures
I'm not sure what to call it yet, but the administrative structure will be heavily upgradable. Higher levels of it will provide additional features, such as attacking invaders, boosting settlement happiness, providing a bonus to research, and diplomacy.
How Big a Region?
The world generator will aim to create regions about 90 tiles on a side, roughly filling a 1920x1080 monitor. Individual regions will vary, of course.