I have had this happen to me twice during survival gameplay.
I can't confirm if this happens to only the command blocks.

Here is what happens:
I place a command block very close to my spawn (basically 0,0,0) with 2 parrots following me. I then set it to go to /tp @p 5000 64 5000. Using a button I trigger the command block and I am teleported.
Please note this part may also be in conjunction with another reported issue?
If the parrots do teleport with me correctly and do not disappear, there is a chance the game changes the parrot's skin to another. Once cyan, to green and one red to grey. Not both birds at the same time but I'd roughly say every 3-5th time one of the parrots will change skin on /tp.

Loading speed was decent during teleportation. I can't notice any other details that might be relevant.