Day 15: Drive to Springsdale, CA as you suggested.
Springdale UTAH is where Dave suggested staying. It is the town located just outside of Zion NP and where you'd look to spend the night of day 14. I don't even think there is a Spring(s)dale in California.

As I mentioned way back near the start of this thread, most National Parks are not very dog friendly, and you are going to be quite limited where you can go within the parks when traveling with your pet. Often times you'll basically have to stick to parking areas, as trails will be off-limits. You'll need to check with each park to see where you will be allowed, and where won't be able to go with your dog. The same is also true with tribal park areas, like Monument Valley and Antelope Canyon.