Some thoughts of mine:
Rather than the Daggerfall region, it might be smarter to use a small province with relatively fewer points of interest as a starting point to generate the road. Maybe Isle of Balfiera, or Lainlyn, Orsinium, etc. A small province near or in a mountainous region could be a good test ground as you would see how the roads behave moving from more even terrain to more rugged and extreme heights. Smaller region would also mean less time spent on generating the roads, and ability to make faster decisions on tweaking the algorithms. Once the model is set up and working as expected, apply it to a larger province like Daggerfall and see how it behaves. Make adjustments as necessary.
Another concern is that certain mods might break the generation algorithm, unless the generation (based on the graph) is sophisticated enough to handle changes in terrain, or recognize a landscape mod earlier in the load order and use those values instead of vanilla terrain coordinates; have an option for the user to regenerate the roads in the mod options screen.
Recognize load order: load the landscapes mod first, then load the roads mod, and have it do a one-time generation of the roads, detecting heights/coordinates based on the landscape mod. Or something like that.
Since the roads would be generated on a preset criteria, it would only need to be generated once, and simply store the values somewhere rather than regenerate the roads every time you load the game. If the landscape mod is changed or removed, allow a player to regenerate the road map, and overwrite the previous values in the mod options screen.
My chief concern is that all the terrain in Daggerfall is procedural, and massive based on whatever seed the devs used originally. So in some cases, the roads mod algorithm would need to be sophisticated enough to detect large changes in height over a short distance (a road should not go up a very steep incline, or straight over a mountain peak for example) to not generate roads over very steep inclines or cliffs. (not that Daggerfall has actual cliffs or plateaus, but you know what I mean)
A road generating mod would need to have some sort of rule or law in place that prevents it from going up too steep an incline, and instead, seek the nearest path of least resistance around the incline. So, you'd need a rule to check for height, avoid creating a road over very steep terrain, and use some sort of lookahead method to find a better route that makes more sense based on coordinates change in height.
Something like that, anyway. Otherwise, you might have an issue of a road texture climbing up a cliff or very steep hill.
Thinking very far ahead, but perhaps road textures could be based on the size of the points of interest's cells somehow. Roads between Daggerfall and another large city might be paved, but roads between smaller backwater towns, inns or temples, might be dirt roads. Maybe a road changes from paved to dirt X distance from a dungeon or crypt point of interest.
I'm just bouncing some ideas out there since this is still all conceptual in nature anyway.
Show off your mod creations or just a work in progress.