In this case the service provider - Twitter - should define it, since they are responsible for implementing any measures against harassers.

Personally, I think any threat of violence - whether this is a realistic threat, or not - should constitute harassment.

A lot of the tweets in that link would qualify. I won't repeat them here, but there are a lot of threats that basically say the tweeter will rape and/or kill the receiver.