What language did Gaius Julius Caesar speak with Cleopatra?

Julius Caesar most likely spoke Latin and Greek to Cleopatra-(with a greater emphasis on the latter).

The Greek language was still widely spoken among the Aristocrats and Patricians throughout much of the Mediterranean and Middle Eastern regions-(including, Egypt). Cleopatra herself, was either of Greek or Greco-Egyptian ethnic origin and so for her, the Greek language would have been her "mother tongue".

In the case of Julius Caesar, he was-(albeit for a short while), the most Patrician of Patricians in Roman society whereby the Greek language was the preferred language among the sophisticates.

When adding the native tongue of Cleopatra, coupled with the preferred language of the Patricians-(such as Julius Caesar), Greek-(and not Latin), would have been the primary form of communication between Caesar and Cleopatra.

(To the best of my knowledge, I don't believe Julius Caesar spoke a word of Egyptian, though it is very likely that Cleopatra, was probably fluent in Egyptian).

Most likely Greek. This is the only language which we know they definitely had in common, and both were highly proficient in it.

High-born Romans learnt Greek and Julius Caesar was no exception:

According to the 1st century C.E. Roman historian Suetonius, Julius Caesar spoke mainly Greek and not Latin, as was the case with most patricians at the time.

Richard A. Billows, Professor of Greek and Roman History at Columbia University in New York, elaborates on Caesar's education:

The formal side of his education consisted of being taught to read and write both Latin and Greek, given a grounding in the classic poets of Rome (Ennius, Naevius, Terence and others) and Greece (Homer, some of the lyric poets, the Athenian dramatists and others), and then taught a smattering of Greek philosophy, but above all the art of rhetoric.

Source: Richard A. Billows, 'Julius Caesar: The Colossus of Rome' (2009)

Cleopatra, being of the Ptolemaic dynasty of Egypt, spoke Greek:

Most historians agree that Cleopatra did not speak Latin and that she spoke Greek, which was her native language. The historian Plutarch was not convinced that she actually did speak Egyptian, and many modern scholars agree with him. Some languages that she may have spoken were Persian, Syrian and Arabic. However, there is no true historical proof that she spoke anything other than Greek.

Plutarch also mentions Ethiopian, Trogodyte, Hebraioi, Parthian and others not specified. One of the latter may have been Latin but we can only speculate on that as,

Plutarch is our only ancient source for Cleopatra’s knowledge of these languages. Note that Latin is not included in the list. It is possible that Latin was one of the many other languages with which Plutarch credits Cleopatra, but Julius Caesar and Mark Antony spoke Greek, so communication would not have been a problem.

Source: Prudence J. Jones, 'Cleopatra: a Sourcebook' (2006)

Duane W. Roller, Professor of Classics, is more open to the idea that Cleopatra spoke Latin but nonetheless concurs that she would have spoken Greek with Julius Caesar and other Romans.

A Note on Plutarch's use of Arabic

Although somewhat off-topic in relation to the question, the mention of Arabic has generated a fair amount of discussion in the comments. This is evident in the academic literature:

The meaning of the term ‘Arab’ in antiquity has been hotly debated for many decades. One reason for this has been the search for a single definition which could be applied to all the numerous references to ‘Arabs’ and ‘Arabias’ in the ancient sources. As noted above, the vast majority of these sources were written by authors looking at the ancient Near East from the outside.

Source: G. Fisher (ed), 'Arabs and Empires before Islam' (2015)

Plutarch's reference probably relates to one of the languages spoken on Arabian peninsula, possibly Nabataean Arabic. Modern scholarship postulates that the spoken form probably predates the written form by several centuries, perhaps as early as the 4th century BC. Consequently, Arab speakers

used other languages for writing, principally Nabataean Aramaic in the north of the Peninsula, and Sabaʾic in the south. Thus an Arabic speaker would either learn the language and script of Aramaic or Sabaic in order to be able to write, or employ someone to write, in these languages for him/her.

Source: Fisher

On the importance of Nabataea to Egypt,

Across the Red Sea was the Arabian peninsula. Although only small parts of it were ever under Ptolemaic control, this region was a vital part of the Ptolemaic kingdom’s economy. The great Nabataean trading center of Petra began to flourish in the late fourth century b.c., and a certain Anaxikrates explored the Red Sea for Alexander, reaching the wealthy aromatics-producing regions at its southern end. By the third century b.c. the trade route from Petra to these districts was well known, and frankincense and myrrh, the two most famous aromatics, were exported to processing factories in Alexandria. Knowing the Arabian language may have assisted Cleopatra in diplomatic and mercantile negotiations, and she may have acquired some Arabian territory in the 30s b.c.

Source: Billows