The purest mathematical justification for why low entropy means a low number of microstates probably comes from the fact that (classical) physical systems are a dynamical systems that preserve the measure induced by the standard metric of the phase space. The measure theoretic definition of entropy then implies the entropy of a partition of the phase space (i.e. a set of macrostates) is indeed the average of the logarithm of the number of microstates.
So indeed if W is the number of microstates in the current macrostate then entropy = log(W) (on average).
And using the typical set you can show that the probability that the average of log(W) over n samples is within 'epsilon' of the 'exact' entropy goes to 1 as n goes to infinity. This is the mathematical justification for the second law of thermodynamics.
The trick is that all of this is true no matter how you partition phase-space. Though that does mean that what is and isn't a high entropy state depends on your perspective.