Why does a decrease in interest rate reduces the velocity of money circulation?
You are absolutely right. Since higher interest rates increase the opportunity cost, you wan't to get rid of it faster (at the margin).

The core of the argument is that the cost stems not only from the amount of money holdings, but also from the duration. Say you are constrained about the amount of money holdings you need in your daily life, but you can still make sure the money is not idle for too long. 

For the second part of your question, you are mixing up concepts. The interest rate influences the Consumption/Savings Decision, but it is the same decision problem as in a (model) world without money, i.e. it is a choice between real variables, whereas money velocity is a monetary question.