The earliest reference I can find to Hercules and Lichas occurs in Hesiod fr. 25, which mentions Lichas in the same context that Ovid does, i.e., Deianara 'having besmeared the tunic, gave it to the herald Lichas to bring" (21-22). This is, of course, treated in the Trachiniae, so both characters are present, but there are no dice games.
Shakespeare knew this story well because he used it in Antony and Cleopatra. Antony says the following after dismissing Cleopatra in anger (Act IV scene 8, 53-61):
... ‘Tis well th’art gone,
If it be well to live; but better ‘twere
Thou fell’st into my fury, for one death
Might have prevented many. Eros, ho!
The shirt of Nessus is upon me; teach me,
Alcides, thou mine ancestor, thy rage.
Let me lodge Lichas on the horns o’ th’ moon,
And with those hands that grasp’d the heaviest club
Subdue my worthiest self. The witch shall die.
I suspect that Shakespeare chose to have Hercules and Lichas play dice for two reasons. First is the surface meaning, as Morochus intends it, viz. to place the greatest of the Greek heroes against a lowly servant in a game not of skill, but chance, in which the superiority of Hercules has no bearing, just as the supposed natural superiority of Morochus is neutralized by the game here. Second, and I think more significant, Shakespeare may also have been prefiguring Morochus's lot, for when he makes his choice, the golden casket, his 'prize' is figurative death (answering the riddle 'Who chooseth me shall gain what many men desire'):
O hell! what have we here?
A carrion Death, within whose empty eye
There is a written scroll! I'll read the writing.
"All that glitters is not gold;
Often have you heard that told:
Many a man his life hath sold
But my outside to behold:
Gilded tombs do worms enfold.
Had you been as wise as bold,
Young in limbs, in judgment old,
Your answer had not been inscroll'd:
Fare you well; your suit is cold."
Morochus likened himself to Hercules in an imagined game with Lichas, but he ended up (figuratively, at least) as Hercules did in the familiar story.