How does the economy "detect" if money is removed from circulation? It is well known that there is a strong connection between introducing more money into an economy and inflation, as well as removing money and deflation.

However, how does the economy as a whole "detect" if money is removed from it?

A similar question would be how it detects whether the supply of money is increased, but that I could understand and explain better as printing new money is regulated, so the government and banks know about the increase and act accordingly. (yes, I know, printing money is not the only way to produce it, but I would guess creating new debt is also regulated or measured in some way)

I could also explain extreme cases, where the amount of money created or destroyed makes up a significant portion of the total amount. If suddenly such a large amount of money appeared, people would start to buy more things, and as the supply of things to buy is not enough, people will pay more money for it to be able to get it by out-bidding others, so prices increase, and we have inflation. Or if a significant portion of the money supply is destroyed, there is an abundance of things to buy, but not enough money to buy things, so prices will have to be lowered otherwise nobody would buy anything, so we have deflation.

However, by what mechanisms does it happen that small (but not negligibly small) amounts of change in the money supply cause small amounts of inflation or deflation?

For example, if one very rich person would sell off some property in cash or take cash out of bank accounts, and just burn or bury that cash without telling anyone, how would the economy "know" it and by what mechanisms would it cause deflation? The amount in this example is not enough for people to consciously realize that money is missing from the economy so they could adapt their spending habits accordingly.
Money is only inflationary in so far as it's moving around. So for there to be an inflationary or deflationary signal, that means that either the amount of money moving around has changed, or its velocity has changed.

And what does it mean to have money "moving around"? It means that it's being used to buy goods or services. And that's how it affects prices - because it affects demand.

So, yes, to elucidate: it's as you say- "if the millionaire wouldn't have destroyed the money but spent it, he could have bought a lot of goods with it, and the sellers of those goods could have bought still more goods with that profit and so on. As now those goods are no longer being bought, the sellers have to slightly reduce prices, so their goods aren't wasted in their warehouses. This means prices will drop a little, and this is how the economy "feels" the difference"