Actual reasons why are never clearly stated, but Corinne Bonnet offers the best theory that it was the lion iconography that led to their identification. From her article in the Encyclopedia of Religion (vol. 9):
In many Cypriot cult sites, a Heraklean iconography, similar to that present on the Syrian coast (Amirth) since the sixth to fifth centuries BCE, is present. It may allude to Melqart, but probably also alludes to other cults, including Reshef /Apollo and some anonym Cypriot god, as if the Heraklean shape were a standard male god iconography. Cyprus was thus a crucial place for the iconographical assimilation between Melqart, the royal god, perhaps associated with the lion (as in the Eastern iconography of the smiting king or god), and the Greek Herakles, who became the god with the leonte, the bow and the club. The Idalion cup (eighth century BCE) is the best illustration of this assimilation process.