I would guess that it is related to the common use of negation alongside the word unless that can still be seen in modern English: for example, "I will not do that unless this happens."
The OED (3rd edn, 2017)'s first definition for unless is as follows:
[†A.] 1. Forming a conjunctional phrase introducing a case in which an exception to a preceding negative statement (expressed or implied) will or may exist: (not) on a less or lower condition, requirement, etc., than (what is specified). Obs[olete].
Here is one of the sentences given as an example for this definition:
a1500 in C. T. Martin Chancery Proc. 15th Cent. in Archaeologia (1904) 59 5 Robert wil not suffre hym to be laten to baile on lasse than he will make..a generall acquytaunce.
You can see that in this sentence, the word "not" is used before (although not directly before) "on lasse then".
Although the word "not" (apparently) often appeared somewhere before "(on) lesse than" in this construction, it did not always: there are other ways to mark a negative statement, and the OED implies that sometimes the negative statement might only be "implied". Here are some of the other example sentences that the OED gives for that definition where the word "not" does not occur before "(on) less then":
1414 Rolls of Parl.: Henry V (Electronic ed.) Parl. Apr. 1414 §22. m. 3 So as hit hath evere be thair liberte et fredom, that thar sholde no statut no lawe be made of lasse than they yaf ther to their assent.
1474–5 Rolls of Parl.: Edward IV (Electronic ed.) Parl. Oct. 1472 3rd Roll §22. m. 24 His land, which many persones..fere to take.., olesse then they myght be made verrey sure of payment.'
1659 J. Sparrow tr. J. Böhme Fifth Bk. Authour i. xi. 87 There was no remedy more, unless then the Deity did move it self.
In the first and last of these, the negation is expressed by the word "no" rather than "not".
I don't interpret the parentheses in the Etymonline entry as saying that the use of "not" is expected to be optional in any particular specific sentence; rather, it's saying that a sentence with "on less/unless" often but not always had the word "not" in it somewhere before the "on less".
(in all the quotations in this answer, bold formatting was added by me for emphasis; it wasn't used in the original sources)