The word handiwork first appeared in Old English, where it was written as two words, hand ᵹeweorc meaning “hand work”. The OED provides this citation:
c. 1000 Ælfric Deut. iv. 28. And ᵹe þeowiaþ fremdum Godum, manna hand ᵹeweorc.
That smattering of Old English might in Early Modern English run more along the lines of “And ye shall worship foreign gods, the work(s) of men’s hands.”
About the word’s history, the OED also writes:
OE. had also handweorc ʜᴀɴᴅᴡᴏʀᴋ containing the simple weorc, work. As ᵹeweorc, iwork did not survive in ME., handiwerc was naturally analysed as a compound of the simple werc, with handi, often written separately, and treated as an adj.: see ʜᴀɴᴅʏ.
Morphologically, that ᵹeweorc there was a past participle form; think modern wrought. In this particular instance ᵹeweorc was functioning as a collective, so more in the sense of works than just plain work. Its curious ᵹe-/ge-/ye-/y-/i- prefix you might recognize from German past participles; it’s the same as we see in the archaic word yclept. Middle English saw OE handgeweorc worn down to things like hondiwerc and handiwork.
Because Modern English past participles did not survive with their Germanic prefix intact, in Late Middle English handiwork = hand + iwork was reanalysed as handiwork = handi + work instead, creating a novel adjective handy and applying it to the noun work.
So our word handy came from people thinking that the y- from the obsolete ywork got moved over to the noun hand in handiwork to make an adjective: handy work. Handy therefore originally meant manual in that it was hand + y, but it has come to mean more than that by extension. handy is more apt to mean “useful” than manual when used standalone.
So yes, handyman is indeed related to handiwork, but not at all in the way one might imagine. The adjective handy came from handiwork through reanalysis, and then later got applied to the various manual labors of a handyman.
The word handicrafts also comes from that reanalysis to create a compound word for craftwork done by hand. Handicap is less clear, however.