The etymology of unless, much like the similar one of lest, does in fact seem rather puzzling, but the archaic first meaning I found in the OED's 2nd ed. (1989) [3rd ed. (2017) differs] confirmed the theory I came up with right after learning that it derives from on less than:
On a less or lower condition, requirement, footing, etc., than (what is specified). With preceding negative, expressed or implied.
So it started with a wording that still makes sense today:
I won't go to the cinema and watch this stupid film with the children on less than [that] you accompany us!
The actual first recorded use in the OED is from a passage in Maundeville (c. 1400) about the antipodes (see the first sentence under Definition 1):
"But þat may not be vpon less þan wee mowe falle toward heuene."
In modernised English: "But that may not be on less than we may fall toward the sky."
Clearly making sense of upon less is the least of our difficulties understanding this sentence today.
Apparently, as often happens with emphatic ways of expressing something, the idiom on less than became so popular and overused that its meaning detached from the individual words, faded and generalised. Uses of on less than in the generalised sense of if not even without it [= the phrase on less than] following a negated statement were recorded just a few decades after Maundeville.
Once on less than had become a full synonym of if not or except, it was natural to leave out the word than, making the etymology slightly obscure even in the original use case and even more so when not following a negation. The path was paved for wondering if the first word was on or un- as they can sound pretty much the same. (I would also expect that even at this early stage people often dropped the word on altogether, as they still often do with [un]less.)
I think what is meant by the negative connotation of unless that facilitated change of on to un- is that unless is now understood as a synonym of if not. Due to some fuzzy thinking this could in fact have made it appear logical that somewhere there should be a negation in unless. But I personally think a much more important factor will have been that on and less were merged into a single word onless, and that un- is vastly more common as a prefix than on-. I think it's normal and quite common for a rare prefix to be replaced by a common one that has essentially the same pronunciation, regardless of any differences in meaning.