You're actually not the first one to ask this question.
The Romans themselves had various explanations to offer. For them, the relation was clear - although they did not necessarily agree with each other. More recently distinguished latinists such as Ernout and Meillet could not rule out the possibility of two distinct homophonic roots ([[3]] - puto).
As for me, I don't have a definitive answer to this one but here are a few dots you might want to connect.
The semantic path here could in my opinion be close to the following one:
Step 0 . Putare as "to purify". The root can be traced to PIE.
N.B. putare is an ancient form; later Latin uses purifico (purus-facio) and purgo. But for now we need to work on puto.
purify => as in "to refine"
Applies to precious metals such as gold and silver.
There is a reduplicative phrase in ancient Roman to emphasize purity for silver:
argentum purum putum
See below.
purify => as in "to clean" or "to cleanse"
Applies to wool and fleece as well.
vellus lavare ac putare
Step 1. from purifying to trimming
- purify => trim/prune
This meaning of "trimming"/"pruning" is still present in present day Italian (potare gli alberi, potare i vitigni) and in derived words such as amputation.
In the Roman world, trimming and pruning is of particular importance for grapevines which are very sensitive to such diseases as mildew and mould caused by various fungi.
In order to prevent these diseases, you need to prune your vines so as to keep them well ventilated and remove the dead growth where fungi thrive.
On this particular subject you can refer to Columella - Res Rustica Book IV - passim. Plenty of advice for wine growers and usages of putare for lexicographers).
Trivia. There was even a dedicated Goddess for these pruning tasks, whose name was Puta.
See this wikipedia article for the name and the hmm... putative etymology of hmm... prostitute in various Romance languages (since you heed Etymological Fallacy that's another question albeit potentially a tad controversial :-).
Step 2. from trimming to simplifying
By doing so you also simplify the structure of the plant which becomes less convoluted (a characteristic of vines in particular and vegetation in general) and easier to... grasp.
Step 3. from simplifying to accounting
Which could (note the conditional) lead to a derived or parallel meaning of "settling accounts" since there is this same idea of slowly progressing to a simplified figure (the account position) through the elimination of numerous details.
Cognates here are of course compute and computer, French compter and whence even account, Italian compiti "homework" and many others.
Step 4. from accounting to forming an opinion
The metaphor from accounting to opinion is a common one in various languages.
Even in Latin: aestumo (I estimate) originally means to assign a value and by extension to form one's opinion.
To value is a bit different because it comes from the concept of strength but Present Day Italian uses valutare as a synonym of "estimate".
Purus and Putus
As I mentioned earlier, Romans also had their opinion on that subject. Here are two examples:
Varro who writes in Caesar's time has this to offer in his book de Lingua Latina (an early "etymological" Latin "dictionary") on the "dispute" entry:
Disputatio et computatio cum praepositione a putando quod valet purum facere. Ideo antiqui purum putum appellarunt; ideo putator, quod arbores puras facit, ideo ratio putari dicitur, in qua summa sit pura. Sic is sermo in quo pure disponuntur verba, ne sit confusus atque ut diluceat, dicitur disputare.
Disputatio ‘discussion’ and computatio ‘reckoning,’ from the general idea of putare, which means to make purum ‘clean’; for the ancients used putum to mean purum. Therefore putator ‘trimmer’, because he makes trees clean; therefore a business account is said putari ‘to be adjusted,’ in which the sum is pura ‘net.’ So also that discourse in which the words are arranged pure ‘neatly,’ that it may not be confused and that it may be transparent of meaning, is said disputare ‘to discuss’ a problem or question.
See also Gellius 7.5
ALFENUS iureconsultus, Servii Sulpicii discipulus rerumque antiquarum non incuriosus, in libro Digestorum tricesimo et quarto, Coniectaneorum autem secundo: In foedere, inquit, quod inter populum Romanum et Carthaginienses factum est, scriptum invenitur ut Carthaginienses quotannis populo Romano darent certum pondus 'argenti puri puti,' quaesitumque est quid esset 'purum putum.' Respondi, inquit, ego 'putum' esse 'valde purum,' sicut novum ' novicium' dicimus et proprium ' propicium,' augere atque intendere volentes ' novi' et ' proprii' significationem.
...
Verbum quoque ipsum puto, quod declarandae sententiae nostrae causa dicimus, non significat profecto aliud quam id agere nos in re dubia obscuraque, ut decisis amputatisque falsis opinionibus, quod ideatur esse verum et integrum et incorruptum retineamus.
The jurist Alfenus, a pupil of Servius Sulpicius and a man greatly interested in matters antiquarian, in the thirty-fourth book of his Digests and the second of his Miscellanies, says: . In a treaty which was made between the Roman people and the Carthaginians the provision is found, that the Carthaginians should pay each year to the Roman people a certain weight of argenti puri puti, and the meaning of puri puti was asked. I replied, he says, that putus meant very pure,' just as we say novicius for novus (new) and propicius for proprius (proper), when we wish to augment and amplify the meaning of novus and proprius.
...
The verb puto itself also, which we use for the purpose of stating our opinion, certainly means nothing else than that in an obscure and difficult matter we do our best, by cutting away and lopping off false views, to retain what seems true and pure and sound.
More Online Sources
[[1]] Charlton T. Lewis, Charles Short, A Latin Dictionary "puto" on Perseus.
Some offline sources
[[2]] 1968 - Oxford Latin Dictionary
[[3]] 2001 - Alfred Ernout, Alfred Meillet - Dictionnaire Etymologique de la Langue Latine - 4e ed.
[[4]] 2008 - de Vaan - Etymological Dictionary of Latin and the Other Italic Languages
P.S. If you find this answer to difficult to understand because it has too much detail, you probably need to trim it... QED :)