Although the gerund can be used to express purpose, it's not allowed in this case because of the direct object Megaram. As stated in Allen and Greenough's Latin Grammar:
The accusative of the gerund with a preposition never takes a direct
object in classic Latin.
They provide more information on the correct usage as follows:
503. When the gerund would have an object in the accusative, the Gerundive is generally used instead. The gerundive agrees with its
noun, which takes the case that the gerund would have had.
parātiōrēs ad omnia perīcula subeunda (B. G. 1.5)
readier to undergo all dangers
Here subeunda agrees with perīcula, which is itself governed
by ad. The (inadmissible) construction with the gerund would be
ad subeundum perīcula; ad governing the gerund, and the gerund governing the accusative perīcula. For details, see §§ 504 - 507,
Your sentence could be expressed with the gerundive as follows:
Hercules viam reliquit ad Megaram petendam.