I played this game when I was about 6-7 (I was born in 1995, so it would be around 1999).
It's was an RPG with mechanics similar to final fantasy and the closest graphics I found to it is Gorky 17 - https://www.youtube.com/watch?v=FCM4qC6E4Q4
You start off on a ship and when you leave I THINK you are on a mountain and you travel down it to get to the next area. I remember the first enemy you fight is a wolf and I THINK you pick up some sort of pipe to kill it with.
You do pick up a woman??? who becomes a member of your team.
I remember the game having a very dreary vibe, the ship you start on (if it was even a ship) was mostly metal and it was painted quite dark. I think it might have been click to move.
I wouldn't be surprised if it was impossible to find the game based on this limited information, but I thought I'd give it a go as it kept bugging me.
Thanks for everyones help