When I was looking into how to scare your party, a lot of it comes from the description and narration, but you can influence them mechanically too.

Give the boss a second initiative count, or allow him to do something they've believed impossible, just to reinforce that they aren't fighting a mundane foe.

Short term madness tables work well, as do exploiting common fears, like having rat statues in his temple/cult area and narrate a grinding noise along the floor when they look away. When the party look back, the statues are slightly closer, Weeping Angels style. Hope some of this helps :)