> Generally it's accepted that the value went up because it became more rare as the number of unit went down.
That's true.
> Or similarly because if all the money represents the price of everything in the economy, as there is less money and assuming that everything in the economy didn't change, then everything has now a slightly lower price.
That can't be true in any meaningful way, because all the money doesn't represent the price of everything in the economy. "Everything in the economy" is always worth many multiples of "all the money".
The definition you'll see in economics is MV = PY. It's defined with reference to the concept of GDP, and the variables are:
M is the amount of money (that year).
V is the "velocity of money", the average number of times that a particular dollar gets spent (that year).
P is the price level. The value of money (that year) is 1/P.
Y is the amount of non-monetary stuff that is produced (that year).
(I would be happier if Y was the amount of non-monetary stuff that existed, but that does not appear to be how economists prefer to talk about it. This set of definitions lets you say that MV is equal to NGDP.)
You can characterize the effect of destruction of money as a reduction in M or as a reduction in V. If you take the view that the money still exists, because it's listed on a balance sheet somewhere, then M has not gone down, but under that view V still has; it's impossible to spend that money. Assuming everyone's urge to spend as a function of their ability to spend stays unchanged, you'll see that the party who locked up $1 million (by destroying it) will, as a result, spend less. Everyone else in the relevant universe is unaffected and spends just as much as they would have anyway. Then, by our special analysis, the amount of total money spent has gone down, and the amount of money in existence hasn't, so the velocity of money has gone down.
Y is unaffected by the destruction of money. For PY to go down while Y stays constant, P must go down, which means that 1/P, the value of money, goes up.
------
Note that the implication of this velocity-based analysis is that, if a miser with tons of money in bank accounts that he'll never use happens to one day withdraw some of that money and destroy it, there will be no effect on the value of money. This is correct; that money had already been effectively destroyed when the miser committed to not spending it.
(Over a much longer term, the effect of destruction would be visible when the miser's heirs inherited a smaller amount of money than otherwise and consequently spent less.)