Оба варианта грамматически допустимы, но дают разную смысловую картину.
- «Он записывал письмо, когда я пришёл.» — несовершенный вид: действие в процессе в момент прихода; фон, продолжающееся или прерываемое действие. Перевод: «He was writing the letter when I arrived.» Временная схема: интервал записи включает момент прихода, т.е. $t_{запись}\ni t_{приход}$.
- «Он записал письмо, когда я пришёл.» — совершенный вид: действие рассматривается как завершённое; либо завершилось к моменту прихода, либо завершение совпало с приходом. Перевод: «He wrote/ had written the letter when I arrived.» Временная схема: время окончания записи $t_{конец}$ не позже момента прихода, т.е. $t_{конец}\le t_{приход}$ (вплоть до совпадения).
Выбор зависит от того, хотите ли вы подчеркнуть процесс (используйте «записывал») или факт завершения/результат (используйте «записал»).