When you knock Gollum off the cliff and he is hanging there, press R2 (or the kill move button). He will fall which does damage. Also, Gollum is not effected by swords. You must parry and push him towards the edge. Once you do so, he should lose his balance and start to fall. He will try to climb back up. At this time, stab his hands with your killing move. It will take awhile to defeat eat him.