The diagram for showing Future-Perfect-In-Past Tense

If you take the "future-in-the-past" meaning of the modal would (which is not its only meaning, but it is the most likely meaning here), then the saying is before the finishing, and according to his intention, the finishing is before the arriving. You cannot tell whether the finishing was actually before the arriving or not; and you cannot tell whether either the finishing or the arriving are in the past.

Like many uses of perfect contructions, the "have" is optional when the temporal relations are clear without it. He said he would finish his task before we arrived is nearly identical in meaning: the only difference is that your sentence sets the temporal focus to our arrival and looks back to his finishing, whereas the form without have doesn't set any particular temporal focus.