I followed him to the city limits.  Within a half hour he had crossed the county line and two hours after that he had reached the state line.  Once he had crossed the border with Tennessee, he felt he was home again.

I do not recall hearing city border/line or county border/limits.  You will hear, however, "on the border between the two cities...", "San Mateo is on the eastern border of Castroville", etc. Surprisingly, borderline is relatively common in many contexts.

His house is on the borderline (border)  between Jacksonville and Greenboro.