This has happened in different worlds. I find a bunch of wolves, I tame them, and I try to walk them back to my home. Sometime they teleport to me after staying too far behind but frequently not. It happens in every type of biome or surface. They mostly fail to follow in extreme hills and during running, but it has happened in flat desert with regular walking as well. In the last game I started with +/- 20 wolves and ended up with 4, over a distance of 1500 blocks, trying to give them time to keep up andf trying to avoid water, as that appears to increase the chance of them not following as well.
Judging from forums I gather that wolves should just be able to follow you during exploration. If this is not a bug, please let me.