I've killed all the salamanders (including Shikata) on the map with Guello (before the Forge room) in Lower Dorn's Deep but he doesn't seem to believe me (he keeps asking me to kill them all). Have I missed something?

Yes, you missed something.

You should talk to Beorn in the Deep Gnome Refugee camp to get the quest to rescue Guello. You can get the quest the second time you talk to Beorn. What's happening to you is what happens when you don't talk to Beorn to get the quest. The game isn't designed to handle this situation correctly. I'm not sure how the quest will play out now that you've started it out of order, nor whether you will get the usual bonus for finishing it.