According to Wiktionnaire, the Vulgar Latin verb tropare could mean not only interpreting a song, but also composing a song or poem. The association of the word with songs remains in words like troubadour. From there, it generalized to inventing something, then to discovering something.
“Interpreting language variation and change” by Kevin Tuite, collected in Language, culture, and society: key topics in linguistic anthropology (2006) has a section on the word, with further references. The verb is not attested in writing, but has been reconstructed from known words and known patterns of sound changes in Romance languages (mostly French and Occitan). Another word based on the same root, contropare, is attested in 6th Century Italy, meaning “compare”.
The etymology of trouver does remain disputed, so it's quite possible that the answer to this question is that there is no connection! Tuite presents a history of this dispute and concludes that “no etymology of trouver/trobar has as yet gained the universal accceptance of experts”. The tropare hypothesis is primarily the work of Gaston Paris. He rejected an earlier hypothesis by Friedrich Diez (later elaborated upon by Hugo Schuchardt) who thought the French word trouver came from turbo, meaning to disturb something; the meaning would then have evolved towards finding something (as a result of disturbing the place where that thing is). This hypothesis is corroborated by the fact that several other Romance languages have a word for find that evolved from words that would apply to finding game during hunting of fishing, and by the fact that trouver meant a chance encounter in Old French (according to the etymology section of the Trésor de la langue française) before it generalized to finding the object of a search, but Paris rejected it because the changes from turbo to trobar (which is attested in many Romance languages around the North-West Mediterranean) would be very unusual.
There are several other hypotheses beyond these two. Albert Kluyver analyzed the known forms contropare and adtropare as well as the Ancient Greek τρόπος and proposed a different semantic evolution: from ruse (attested for τρόπος), to making up a ruse or lie, to inventing, to discovering. This meaning explains contrive from contropare rather well. Julián Ribera y Tarragó suggested a completely different origin, from an Arabic word taraba meaning to sing; this directly explains troubadour, and trobar/trouver would have followed the same evolution compose → invent → discover that I mentioned earlier. Maria Rosa Menocal in The Arabic Role in Medieval Literary History: A Forgotten Heritage analyzes this hypothesis and concludes that it is plausible on both phonological and semantic grounds, and more likely than the tropare and turbo hypotheses, but was unfairly disdained by 19th and 20th century Romance language scholars because they did not admit Arabic etymons readily.