Elfrith is not in a mine nor broken valley. He is on sentinel island, which is quite near to the ship crew camp. He was forced up onto some pillars cause being surrounded by some dragon elf. When you get close to his location, he will automatically ask you for help and when you rescue him, you get a quest item which allow you to continue on with the main quest.
