By the rules, yes, but this can cause problems.
I've seen an orc chief with combat reflexes begin to cut down his orc minions with AoOs as they passed by because the invisible enemy barbarian/rogue (with combat reflexes and great cleave) was getting to cleave into him every time one of his minions passed by him and into the swatting range of the spiked chain wielding invisible rogue.
If you think this is a problem, I've seen a few house rules that deal with the issue:
1.) No cleaving off an AoO.
2.) No cleaving off an AoO, but if you fell someone on an AoO, you gain a bonus AoO to be used before your next turn (effectively allowing you to 'cleave' into someone else that is also provoking an AoO). (Note: For those people that see the round based system as an abstraction and prefer to think of combat as everything happenning in real time, this rule makes sense. To others, it is just weird.)
3.) Cleaving off an AoO is ok, but you may only cleave into a particular target 1/rd.
4.) Every time you cleave into something, you must stand up and scream "CROM!!!!!" If it is during your AoO, you must instead leap to your feet and sing a Tom Jones tune with an accent of your choice (selecting a different song and accent for each cleave).
I use #2. Well, I use #2 most of the time, but every once in a while #4 slips into the game.