However, what if one of our models (for example, the Mallows model) has a permutation, plus some real-valued parameters instead of just real-valued parameters? I can still maximize the likelihood over the model parameters, for example obtaining a permutation $\pi$ and a parameter $p$. However, how many parameters does $\pi$ count toward for computing AIC/BIC?
Intuitively, I suspect that the set of all permutations on $p$ elements is equivalent to $p^2-2p+1$ parameters.
This is because the permutation matrices are the extremal points of the convex space of doubly-stochastic real matrices of rank $p$, and in general the doubly-stochastic matrices have $p^2-2p+1$ parameters (you get $2p$ constraints because all row sums have to all be 1 and column sums have to all be 1, but one of these is redundant, so you have $2p-1$ constraints on $p^2$ entries).
I have no proof, but it seems right. Maybe it's worth trying it numerically?