There is a trick that may help, but it can still take ages and be rather expensive.
Firstly stock up on repels. (Stop all pokemon lower than your lead appearing)
Then pick a route with low level pokemon.
Put a pokemon that is a higher level than the pokemon on the route but a lower level than the dog you are trying to catch first in your team. (Dog can appear but not route pokemon)
Then go in to the route use a repel and walk round until it runs out.
When it runs out leave the route, then walk back in again and repeate the step above. (If the dog isn't on the route you are on walking out and in again will force it to change location)