I am curious whether
헤다 are related. However, if they really are related, where does that
헤엄치다 come from?
헤엄치다 can be analyzed as 헤엄 + 치다.
헤엄 is a noun that means "swimming", as seen in these sentences:
나는 바닷가 마을에 살면서도 낚시와 헤엄을 배우지 못했다. "I did not learn how to fish or swim even though I was living in a seaside town."
헤엄을 못 치는 몇몇 사병들은 뗏목이나 드럼통을 타고 주로 밤에 강을 건너왔다. "A few soldiers who can't swim crossed the river to us mainly at night, on a raft or a drum can."
It is related to 헤다 "to swim" by etymology:
헤다 "to swim" + -옴 (Middle Korean gerund suffix) > Middle Korean 헤욤 "swimming" > Early Modern Korean 헤염 > Modern Korean 헤엄
치다 (Middle Korean 티다) is a delexical verb that is used to describe any abrupt kind of action.
'헤다' has multiple homonyms, and one of them is 'to swim.' However, it is a rarely used word. Korean speakers usually use the word '헤엄치다' to mean 'to swim.' Two words '헤엄치다' and '헤다' do not have the same etymology.
The original form is '혜옴티다', then 'ㅖ' changed to 'ㅔ', 'ㅗ' to 'ㅓ', and 'ㅌ' to 'ㅊ'.