So there's been a lot of lamenting and gnashing of teeth over the supposed inaccuracy of the egg distance tracking. I think this all stems from an incorrect assumption of how Pokemon Go tracks distance. I realised I've got so used to how Ingress does it, that it didn't even occur to me that others might not realise and would be wasting time doing it the 'wrong' way. So let's begin
Pokemon Go does not use a pedometer/measure steps
This one I verified purely by chance, but I suspected was the case anyway. I was playing Go at the office and had a blip in my GPS. My avatar jumped halfway down the street, but before the GPS resolve itself and my avatar returned to where it was, an egg hatch triggered. I hadn't touched my phone, it hadn't moved or been nudged. But it had, according to my GPS, moved 500 meters down the road. And that's what triggered the egg hatch: distance not steps
Distance tracking doesn't work how you think it does
Many people are assuming that distance tracking, while the app is open, works like apps like RunKeeper or Strava; the app measures your exact route, every turn and deviation, every meter. This is not the case; Pokemon Go appears to work like Ingress (unsurprisingly), using refresh displacement measurement. What this means is Go notes your location, then waits an amount of time. After that time has passed, it measures your location again and works out the straight line distance between the two points.
What this means is, if you're walking a weaving path, back and forth, and happen to be quite close to your starting point after the first location check, it won't measure the entire distance you've walked in the intervening time. It'll just measure the straight line distance, which can be considerably less.
I verified this over three days; I spent my lunch walking around a my local park (which I know the circumference of) and observed the egg progress in the app, which was running the whole time (this is important, the app only tracks while open). The egg progress didn't go up as much as my actual distance, which is the issue people are reporting. Then yesterday, I carefully measured my walk to work progress. 1.6km in a pretty much straight line. All my eggs got 1.6km progress. Did the same thing today, 1.6km walked, 1.6km tracked.
tl;dr Egg distance tracking is not continuous tracking, so walking in circles will take longer. Better to walk in straight lines.