He can be tricky to find. He appears in Helluland and is the only Orc that appears as a Marauder in the area.
He seems to be found usually in the x coordinates between 300 and 500, but this is not confirmed.
He is classified as a Leader, you may need a group in order to be successful.