He does need some more damage.
Nautilus is an extremely disruptive champion; between the pull on his Q, the root on his passive, the slow on his E and the knock up on his ultimate, he's a pain in the ass for the enemy team. The problem is that past the laning phase, pretty much all of those save his ultimate can be ignored; the anchor is too hard to land except for an initiation and doesn't pull things through walls, the slow on his E is pathetic, the root and bonus damage from his passive are laughable and the bonus damage on his W doesn't even register. The design philosophy behind him was that he would use his W, giving him a shield and massively increasing the damage he deals, forcing the enemy team to either focus Nautilus for a while to reduce the damage he does or take a lot of damage from him; however, the damage he does is just not enough to matter. There are several reasons for this:
-
He can't afford to build damage. The only tanking ability he has is a damage shield on his W and it's not even that good. If he doesn't build all out tank, he won't be tanky enough.
-
Piss poor ratios and base damage on his abilities. The base damage on his abilities is so low it's insignificant. However, this is compounded by the fact that even if he builds AP, his ratios suck too much for his damage to scale. This means it's usually a better idea to skip damage entirely and just focus on being tanky as hell.
-
Immense cooldowns on his abilities. All of his abilities, without exception, have long, LONG cooldowns. It's understandable for his Q, his E, his ultimate and even somewhat his passive to have such long cooldowns; there's no excuse for a long cooldown on his W however. This is compounded by how mana hungry he is, meaning that even with the long cooldowns, you're constantly running out of mana.
He needs more damage, plain and simple. That or he needs to be tankier, which would allow him to build damage items.