The question illustrates three separate German verbs that are easily confusable, and have closely related meanings: the two phrasal verbs herumspazieren and spazieren gehen, and the simple verb spazieren.
- According to Duden herumspazieren is colloquial, and means 'to amble here and there without a clear aim' ("hierhin und dorthin spazieren").
- Spazieren gehen is not considered to be colloquial, and simply means 'to go for a walk' ("einen Spaziergang machen").
- For spazieren, Duden distinguishes two meanings. The first is basically synonymous to herumspazieren ("gemächlich [ohne bestimmtes Ziel] gehen; schlendern"), the second one is a synonym of spazieren gehen. The latter meaning is marked as outdated ("veraltend").
Note that the degree to which they are interchangable is very gradual. I suspect that speakers will generally find ich gehe mit meinem Vater spazieren fully acceptable, but fewer may like ich spaziere mit meinem Vater herum, and ich spaziere mit meinem Vater may be rejected by quite a few. Yet, if you add an adverbial, I think their acceptability is greatly improved:
Ich gehe mit meinem Vater im Park spazieren.
Ich spaziere mit meinem Vater im Park herum.
Ich spaziere mit meinem Vater im Park.
At least to me, all three are fully acceptable. If pressed to define the meaning difference between them, I'd agree that the first is more directed (perhaps even following a marked route), whereas the other two have a much more spontaneous ring to them.
As to the regional differences, I think that the simple verb spazieren may be more frequent in southern varieties of German, whereas northern German varieties may have a preference for the phrasal variants.
Some support for this hypothesis comes from Google queries: Out of the ~39400 hits for the query string
"spazierte *" site:at, ~3250 hits also match the query string
"spazierte * herum" site:at. This means that less than every tenth occurrence of spazierte (about 8 percent) is followed by herum if the search is restricted to websites that are associated with the Austrian
.at top-level domain.
If the same searches are conducted for the
.de top-level domain, which is associated with Germany, the proportion is very different: out of the ~167000 hits for
"spazierte *" site:de, ~67200 also match
"spazierte * herum" site:de, i.e. about 38 percent. In other words, the probability that spazierte occurs together with a following herum is more than four times as high for
.de domains than for