Using wall-crossing formulae and the theory of mock modular forms we derive a holomorphic anomaly equation for the modified elliptic genus of two M5-branes wrapping a rigid divisor inside a Calabi-Yau manifold. The anomaly originates from restoring modularity of an indefinite theta-function capturing the wall-crossing of BPS invariants associated to D4-D2-D0 brane systems. We show the compatibility of this equation with anomaly equations previously observed in the context of N=4 topological Yang-Mills theory on P^2 and E-strings obtained from wrapping M5-branes on a del Pezzo surface. The non-holomorphic part is related to the contribution originating from bound-states of singly wrapped M5-branes on the divisor. We show in examples that the information provided by the anomaly is enough to compute the BPS degeneracies for certain charges. We further speculate on a natural extension of the anomaly to higher D4-brane charge.