The game is
Man O'War: Corsair. It's a mix of
Naval Action and
Mount&Blade, set in the Warhammer Fantasy universe. You explore the world, trade and fight all kinds of enemies, including gigantic monsters like the Megalodon.
Mr. Sharky decided to have my proud ship, the
Bloody Maid, for dinner but we fought him off. And had sharkfin soup for the next six months.