It works for single weapon and dual-wield style. It would work for your situation, but the mace would make it look silly.

With mace:
http://www.youtube.com/watch?v=hqc7L3VSCWo

With dagger:
http://www.youtube.com/watch?v=hlCqveu1-60

I use a two-handed warhammer, and it's awesome I'm normally not the bloodthirsty type, I tend to turn gore off, but there's just something really satisfying about whacking the head off an enemy with a huge hammer.

So does decapitating someone just after they say "I will destroy you"

It's a great perk for the damage bonus and the decap animation is great w/my preferred weapon which is a glass war axe.

Often times, the head is still saying something like, "you never should have come here" while it is falling to the ground. That's always good for a cheap laugh.

Many (if not most) of the level 100 perks are absolutely abysmal. When you get to 100 you just go "thanks for nothing" and hang your head in defeat.

I started a new character last night, and I'm thinking that I'm going to have him using 2-handed Warhammers (for the, what is it, 75% armor-bypass?). I'm guessing that you can't cut someone's head off with a blunt warhammer? But, do I at least still get the 25% damage bonus to the power attack, without a bladed weapon? I'm cool with that. I figure that at 2.25X base damage (100% from the 5 levels of the basic 2-handed damage perk and the 25% power attack bonus), where the "base damage" is greatly increased by my smithing, plus a 75% armor bypass, means I'll be quickly killing most enemies even without the occasional insta-kill decap. (I also plan to eventually add enchanting to my skillset, but I'm saving that for later, so I can concentrate on 2-hand, heavy armor, smithing, and resto (for heals/stamina).

could use more than just decaps

You still get the +25% bonus, yes. And if it's anything like maces, you'll still be able to knock their heads off, lol.

Ive had it for at least 5 hours of gameplay and have not seen one head come off yet...Has not been worth it.

The perk is worth it for the damage, for me it kicks in about 1 every 4 kills, so does come up a fair bit. You have to remember tho, it's only standing power attacks, you can not be walking/moving.

+25% damage to standing power attacks are not worth it? Are you sure you've been doing standing power attacks? That means not using any directional keys. I get it at least 1 in 4 or 5 kills.

Bandit leaders usually take me 2-3 power attacks to kill, and noticed with that perk, I sometimes 1 shot their heads off.

So it may add a small insta kill pecent to your standing power attacks.