Compare the villains in Star Wars A New Hope with the ones in the Phantom Menace.
In the New Hope, the Imperials quickly storm the spaceship, leaving the hallways carpeted with dead rebels, then Vader crushes a man's throat, then his soldiers land, massacre a bunch of jawas and burn Luke's family to death. Then they blow up a planet. This all happens relatively quickly.
In the Phantom menace...no human being dies until the end. All the violence is between incompetent robots and annoying rabbit people. We are assured that 'people are dying' repeatedly, but this is never shown.
So you really have to show something. If your villain is making threats, why not have some of them manifest? If the villain can't make good his threat to kill the hero, he can still kill everyone in the hero's village, leaving their heads on pikes. He can still saw off the kindly old conselor's hands and nail them to his head. He can drown an entire county to make way for his industrial hydro power plant reservoir. Sacrifice some minor characters, or even major ones if you are in a Martin mood.
So long as your villain's motivations are clear, let him be as nasty as you can imagine. Don't have him do evil things just to be evil, which is really common for when people write themselves into a corner and find that their villain is too sympathetic. They should always have a motive. A good villain treats people like things. If they are useful, he uses them. If they are obstacles, he eliminates them.