That said, mature themes or not, I'm pretty sure Madoka is a magic girl show isn't it? I mean, it might not be for children but it certainly features a story dominated by young girls with magical powers who transform into costumes. I mean, it's no sailor moon but the basic premise of magic girl still applies from what I can tell.
Yes and no. I don't want to delve into spoiler territory (puls I'm lazy and also it's been a while since I watched Madoka), so I'm gonna be vague here...
Yes because, out of the 5 lead "Magical Girls", most of them readily use their Magical Girl powers, which most certainly entails Magical Girl costumes... though it's not like Digimon (perhaps Sailor Moon as well? dunno never seen it) where the show is chock full of transformation sequences.
No because, contrary to Roger the Horse's claims, Madoka most certainly is a deconstruction of the Magical Girl genre. To quote TVTropes:
"Puella Magi Madoka Magica is, for the majority of the series, a pretty thorough deconstruction of the Magical Girl genre. The premise starts simple. Young
Naïve Everygirl Madoka and her
Wide-Eyed Idealist friend Sayaka, are approached by
Mentor Mascot Kyubey, and the relative
Cool Big Sis Mami, where they are given the opportunity to become
Magical Girls. In exchange, they are granted one wish, that can be anything they want, but they will have to fight demonic entities called witches for the rest of their lives. In addition, a
Dark Magical Girl, Homura, is opposed to this, and is constantly trying to prevent the two from making a contract. Sounds reasonable enough. Then the show demonstrates exactly what happens to those young girls who are forced into fighting
Eldritch Abominations with no chance at a normal life."
The main problem I think I have with the anime I've watched is that now I find most monsters utterly disinteresting. I was watching Troll Hunter earlier, and although I thought it was a good movie, I couldn't help but feel that the trolls just seemed way too comprehensible. Give me
Leliel or
Walpurgisnacht any day of the week.
Then you might wanna check out
Eldritch Abominations on TVTropes...