The Melee Damage perk increases the melee damage of the King and all the units by 35%.
You, your units and all of your buildings start the game with +35% melee damage.