What is the first recorded dog name?

A hunting dog (tesem) named Akbaru is depicted in the tomb of the Fourth Dynasty pharaoh Khufu (died c. 2566 BC).

There is a stone relief dated to circa 2400 BC from the Fifth Dynasty showing a dog called Beha, probably a greyhound. The name Beha is

possibly an abbreviation of "behkai" (oryx antelope), a dog's name known from other contexts

Beha, Fifth Dynasty. Source: Walters Art Museum [Public domain], via Wikipedia

Beha was also the name of one of the dogs of the Eleventh Dynasty pharaoh Intef II (c. 2112–2063 BC); the dog's name was carved on an individual stele.

In the Sixth Dynasty (c. 2345–2181 BC), a guard dog named Abuwtiyuw was buried with his own stele, sometime before 2280 BC (unfortunately, it cannot be more precisely dated as the stele was reused in another construction so its original location is unknown). The (translated) inscription on it reads:

The dog which was the guard of His Majesty. Abuwtiyuw is his name. His Majesty ordered that he be buried (ceremonially), that he be given a coffin from the royal treasury, fine linen in great quantity, (and) incense. His Majesty (also) gave perfumed ointment, and (ordered) that a tomb be built for him by the gangs of masons. His Majesty did this for him in order that he (the dog) might be honored (before the great god, Anubis).

Source: George A. Reisner, 'The Dog Which Was Honored by the King of Upper and Lower Egypt'. In Bulletin of the Museum of Fine Arts Vol. 34, No. 206 (Dec., 1936)

Inscription of the Dog Abuwtiyuw. Source: Archaeologist Ticia Verveer

As to the meaning of the name,

According to Reisner, the name "Abuwtiyuw" is not fully translatable, but he surmised that ꜥbw ("abuw") is an onomatopoeic representation of a dog's bark, as this component often is found in Ancient Egyptian dog names.26 Edward C. Martin Jr. claims that the name means "With Pointed Ears", which would fit the description of the Tesem.2

According to Reisner, Abuwtiyuw's breed was the "greyhound or slugi (called tsm in Egyptian)." Other dog names also survive from Ancient Egypt, though online sources do not give dates for the following:

We even know many ancient Egyptian dog’s names from leather collars as well as stelae and reliefs. They included names such as Brave One, Reliable, Good Herdsman, North-Wind, Antelope and even “Useless”. Other names come from the dogs color, such as Black, while still other dogs were given numbers for names, such as “the Fifth”.

In Ancient Egypt, dogs commonly bore the same names as humans, while some had theophoric names (names which included the name of a god). Dogs,

particularly the hunting dog or greyhound, played an intimate part in the daily life of the kings and nobles of all periods in ancient Egypt.

Source: Reisner

In Ancient Greece, dog naming was common. The Greek writer Xenophon, in Cynegeticus ('On Hunting', late 5th / early 4th century BC) gives a list of dog names he thought suitable:

Give the hounds short names, so as to be able to call to them easily. The following are the right sort: Psyche, Thymus, Porpax, Styrax, Lonchê, Lochus, Phrura, Phylax, Taxis, Xiphon, Phonax, Phlegon, Alcê, Teuchon, Hyleus, Medas, Porthon, Sperchon, Orgê, Bremon, Hybris, Thallon, Rhomê, Antheus, Hebe, Getheus, Chara, Leusson, Augo, Polys, Bia, Stichon, Spudê, Bryas, Oenas, Sterrus, Craugê, Caenon, Tyrbas, Sthenon, Aether, Actis, Aechmê, Noes, Gnomê, Stibon, Hormê.

The meanings of some of these names are explained in a footnote:

The names are significant of the colour, strength, spirit, sagacity or behaviour of the hounds. Hebe and Psyche are still in the list of bitches' names, and modern equivalents of several of the other names are in use, e.g., Lance (Lonchê), Sentinel (Phylax), Ecstasy (Chara), Blueskin (Oenas), Crafty (Medas), Hasty (Sperchon), Vigorous (Thallon), Impetus (Hormê), Counsellor (Noes), Bustler (dog) or Hasty (bitch); cf. Sperchon. For Πολύς we should probably read Πολεύς, “Rover.”

Given that dogs were domesticated many thousands of years before even the Fourth Dynasty in Egypt, it is quite likely that dogs were being given names before any of the ones mentioned above. However, there do not appear to be any older known names for non-mythical dogs than those from Ancient Egypt.

In mythology, NKCampbell mentioned Panhu in a comment; Panhu was supposedly the dog of the Emperor Ku (possibly reigned c. 2436 BC to c. 2366 BC though some classify Ku as semi-historical). In legend, Panhu killed an enemy general and married Ku's daughter. Another mythical dog is Sharvara (meaning 'variegated or spotted') from Hinduism (mentioned in the Vedas) and belonging to Yama, the lord of death and of justice. This mythical dog was one of two which "guarded the gates of the netherworld."

(All emphasis is mine)