I would say "labelled him an idiot". Yes, you could describe it thus. To me, "labelled" has a stronger sense that Mary thinks he's an all-round idiot by nature (rather than just being idiotic on one occasion, say).
New words, one handy idiom, and a 2-minute quiz — delivered to your inbox to keep your streak alive.
New2grammar'as' is optional.
Can I describe the situation above as Mary labelled him (as) an idiot?