You can calculate which attribured will be improved the most at every level up before you even buy the mercenary.
Just divide each of their attributes (without items) by their level. That's how many points they will gain at each attribute every level up. I've seen from 1 up to 5 points per level.
Skills don't get improved by levels, that's why generally you'll need a new set of mercenaries in every tier.