I guess I can somewhat see the connection, but it seems tenuous at best. How did this phrase originate and become so widely used?
So the word late itself has an interesting etymology. Old English læt, meaning "occurring after the customary or expected time," originally meant "slow, sluggish, slack, lax, negligent," which came from Proto-Germanic lata (source also of Old Norse latr "sluggish, lazy," Middle Dutch, Old Saxon lat, Dutch laat, German laß "idle, weary," Gothic lats "weary, sluggish, lazy," latjan "to hinder"), from Proto-Indo-European (the hypothetical reconstructed ancestral language of the Indo-European family) led "slow, weary" (source also of Latin lassus "faint, weary, languid, exhausted," Greek ledein "to be weary"), from root le "to let go, slacken".
As to the source of its meaning as "deceased", around mid-13c. it was used meaning "occurring in the latter part of a period of time." From c. 1400, "late" was seen as meaning "being or occurring in the near, or not too distant, past; recent" (of late). From this comes the early 15c. sense "recently dead, not many years dead" (as in the late Mrs. Smith).
The OED does weigh in, actually. As Stephanie Kaye Turner points out, late meaning deceased (which has been used since at least 1490) seems to have come from using late as an adverb (where now we might use lately) to mean "not long since (but not now); recently (but no longer)." We see this adverbial use in Hamlet: "A clout about that head, Where late the Diadem stood."
The OED's earliest use of it referring to a deceased person is found in Caxton's Eneydos (1490): "Her swete and late amyable husbonde."
I can imagine its widespread use is due to its formality in comparison with the word dead. It seems much more appropriate as well as respectful to reference the late Mr.Smith than the dead Mr.Smith. The grave nature of the word dead is avoided especially in the context of sensitive situations. This is where terms like "deceased", "passed away", or "late" are more preferred, leading to their widespread use today.
According to this, the usage of the word 'late' as to mean 'deceased' started in the early 15th century.
In the 13th century, the word bears the meaning: "occurring in the latter part of a period of time.", which then was derived to "being or occurring in the near, or not too distant, past; recent" (of late) in the 14th century.
Then in the 15th century, the meaning of the word 'late' was derived further to be an adjective that indicates that a particular person was alive in the past recently, but not anymore.