What's the origin of the rule that composes the adverbial forms finishing in -mente (e.g. velocemente, normalmente, assolutamente, diversamente etc).
Is it somehow connected to mente (Latin mens, English mind) substantive?
Yes, it is. It continues the ablative form of Latin mens, which is indeed mente. So felicemente would have started meaning something like “in a happy state of mind.” (See for example the Treccani article about “-mente”.)
You are on the right track. It is indeed true that those words ending in -mente, which are always adverbs derived from adjectives, take their origin in the Latin mens (mind, but also spirit, intelligence, thought).
This is because in Latin itself, a construction like "A + mente" meant "with an A mind," where A is an adjective.
Starting from this, the word mente came, in Italian, to be attached directly to the adjective to create a new adverb.