NSTimeInterval interval = 326.4;
long min = (long)interval / 60; // divide two longs, truncates
long sec = (long)interval % 60; // remainder of long divide
NSString* str = [[NSString alloc] initWithFormat:@"%02d:%02d", min, sec];
Спецификатор формата% 02d дает двухзначное число с начальным нулем.
Примечание: это только для положительных значений интервала.