Files you absolutely must change to add region:
*descr_regions.txt
*data/text/campaign_name_regions_and_settlements_names.txt
*map_regions.tga

Files you really should alter:
*descr_strat.txt
(to add the region under the appropriate faction - BI will actually still run if you don't do that - new settlement will be slave village, RTW won't run if you miss this step)

Map files you may need to alter:
*map_heights.tga - to add landmass under your new region if you're extending out into what was previously sea - if you do need to alter this file delete the map_heights.hgt if there is one or changes won't show up.
*map_ground_types.tga - if for instance you've put your new town position on top of inaccessible mountain or forest.
*map_features.tga - only if you've parked your new town position on top of river / cliff /volcano and need to move the feature.
(you should be getting error message if you've placed your town on some sort of inaccessible terrain)

You may also want to eventually add your new settlements to
descr_mercenaries.txt and maybe even descr_win_conditions.txt
but you definitely don't need to do that to get map working.