The legend of Carn Cabal is likely to be a so-called "onomastic legend", that is, one which explains a name. Historians Rachel Bromwich and Simon Evans have suggested* that Cafal (pronounced "Caval", and previously written "Cabal" as in the Historia) is related to the British word for a horse, not a dog (Cafall "horse" from the Latin caballus* cp. one modern Welsh word for "horse" ceffyl, cf. ci/ki "dog"). As it seems unlikely Arthur would have called a good hound "horse" (unless it was as fast as one) it would appear on the strength of this that the cairn name came first, and the dog was given the name of the cairn without a thought to the origin because of the wonderful paw-print. As further evidence Bromwich and Evans note the double meaning of carn as both "cairn" and "hoof" and the fact that two places in Meirionnydd (Area) are named Carreg Carn March Arthur ("The rock cairn/hoof of Arthur's Horse"): probably the rock next to Llyn Barfog [Info : Map : Photo] and that at Loggerheads [Info/Photo : Map : Drawing], both of which are associated with legendary hoof-prints of a similar type.
This suggestion is strengthened by the initial mention of Cavall (Kauall *line 337 / Cauall *line 739) in the tale of Culhwch and Olwen (Details) as one of the three horses (meirch *line 337) of Bwlch, Chyuwlch, and Seuwlch, the sons of Kledyf Kyuwlch - the first two being Call ("Sharp/Wily") and Kuall ("Speedy")* (cf. Guest's translation*, which suggests a less-likely punctuation that renders these animals dogs).
Yet, in the tale, by the time Arthur is hunting the boar Ysgithrwyn Ben Beidd, Cavall (Chauall *line 1015, *line 1108 / Kauall *line 1021) is his dog, and, indeed, kills the boar. Cavall then goes on to help Arthur hunt the giant boar, the Twrch Trwyth. Bromwich and Evans have suggest that once the cairn had been associated with the dog by the list in the Historia, the name would have easily been picked up by the author of this tale*. This is further picked up in the tale Chwedl Geraint fab Erbin*. which mentions Cavall as the name of Arthur's dog.
As the Visit Details show, there is plenty of potential for finding dog-sized prints in the area, but this doesn't extend to horse-hoof sizes, possibly demanding the name, originally associated with a horse, became linked with the dog. There has, however, been no evidence of horse-burials or similar from the area so it is not clear what the origin of the name is either way. One faint possibility may be that "Cabal" is, instead, related to the Latin root Cap which forms words about snatching and seizing, including our "capture", and that the dog name really did come first.