Why does a decrease in interest rate reduces the velocity of money
Keep in mind that money circulation and velocity of money circulation are different concepts. The relation you point out in your 2nd paragraph applies to money circulation, not its velocity: A high interest rate renders saving more attractive and thus reduces money circulation. Also, it is more useful to think of this in terms of "increase of money supply" rather than "decrease in interest rate".
The Wikipedia article you cite defines velocity of money circulation as
the frequency at which the average same unit of currency is used to
purchase [something] within a given time period.
The key term is "average same unit of currency". An analogy with drivers and cars is illustrative:
Drivers demand cars (currency) so they can "visit destinations" (purchase goods and services). Suppose the central bank releases additional cars, thereby making them more affordable during a given period.
The release of additional cars will lead to an increase of drivers' aggregate mileage, but the frequency and average usage of one same car within that given period will decrease because now drivers have more cars (units of currency) to choose from [to perform their transactions]: If now you have access to five cars instead of just one, you might certainly end up driving more than you used to, but you are very unlikely drive five [, six, seven, ...] times more than when you had access to just one car. That means that, in average, your usage of one same car will be lower than that from when you only had one.
The implication on the frequency of average usage of the same unit follows directly from the above argument.
An increase of money supply reduces the velocity of money circulation also from the standpoint that economic agents will not necessarily spend all the additional money available. They will save a portion. That portion pushes down the frequency at which the average same unit currency is used for purchasing goods and services.
Lastly, the Wikipedia section of Relation to money demand is flawed. It states in relevant part:
Given the nominal flow of transactions using money, if the interest
rate on alternative financial assets is high, people will not want to
hold much money relative to the quantity of their transactions—they
try to exchange it fast for goods or other financial assets, and money
is said to "burn a hole in their pocket" and velocity is high.
That argument is flawed because it implicitly assumes that a low interest rate associated to money supply can coexist with a high interest rate on alternative financial assets: That creates arbitrage opportunities. In reality, both rates have a positive correlation. When alternative rates are high, people could not hold much money anyway because the interest rate associated to money supply is also high.