Well this is how i did his quest during my 1st play through, which I think more efficient on the exp. I ignore his quests till almost clear off sentinel island, as I think if turn in his heart too early in the game, it will just be waste on exp which I get from mob. As everyone should notice, when your level is higher than mob, exp drops and there plenty mobs in broken valley for exp. So I decide to turn in goblin hearts during late sentinel island period, which still bring good exp. I think I had accumulated bout 50+ hearts in broken valley and choose to kill him after turning in all hearts. And not bad too for an extra stats points, even though killing him give crappy exp due to level difference.
There are more goblins in orabas fjords, but I dont think you can obtain any hearts from them. You can always try if you want to, and the goblins there has level range of 18+ and above.
