I'd say no less than 6 days (or 5 locations per turn). Any lower than
that and I think you are moving just too many provinces per turn,
especially if you add a bonus for horses and such. I think you should
never take less than 3 days to travel from one place to another
unless, perhaps, you are flying or are using a gate. That is 10
locations per turn and quite fast enough...
John Morrow