Derry gave Mayo a fright in Castlebar but the Connacht giants eventually prevailed by 2-21 to 1-13 after extra time.
It was 1-12 each at the end of normal time but the winners bossed the two extra ten-minute periods to progress to the next round with plenty to spare in the end.
Damian Barton's charges were the better team before the break and were full value for their narrow 0-8 to 0-7 interval lead. They could also consider themselves very unfortunate not to have found the net at least once curing that passage of play.
Cillian O'Connor's free from the hands had the hosts ahead inside 50 seconds but Niall Loughlin's tap-over free had the Oak Leafers level on six minutes. By that stage, the nonplussed northerners had also created two goal chances, struck the woodwork and missed a straightforward free.
Andy Moran collected a great Kevin McLoughlin pass to restore Mayo's lead but the lively Loughlin dropped over an excellent leveller in the tenth minute. With the visitors giving as good as they were getting, Benny Heron tore through the centre to smash over the lead point and Ryan Bell swiveled to make it double scores, 0-4 to 0-2.
O'Connor's second free closed the gap at the midway stage in the first half and Ben McKinless did well to deny O'Connor with his feet from close-range after he'd fisted a Moran point effort onto the upright.
After Loughlin and O'Connor swapped frees, Derry were left ruing their luck when Carlus McWilliams' shot hit David Clarke then rebounded off his shin and onto the foot of the post … within seconds Lee Keegan had Mayo level, 0-5 each.
Bell arrowed over a superb lead point in the 28th minute; O'Connor (free) equalised after Aidan O'Shea was dragged down; Loughlin's third successful free at the other end had the underdogs back ahead with four minutes left before the break.
O'Connor and Loughlin traded injury-time frees as the Foylesiders kept their noses in front at the short whistle.
Bell kicked his third brilliant point in the first minute of the second half but Mayo were quickly level when Moran pointed and O'Connor followed up from a free after a disastrous McKinless restart. With the sides locked on 0-9 each, Keegan fisted an attempted point onto the crossbar and O'Connor poked a groundstroke across the face of the Derry goalmouth before also dragging a free wide.
Midfielder Danny Heavron brilliantly edged the Oak Leaf County back in front via the inside of the upright in the 47th minute and Moran thumped a shot off the post when Derry's net looked about to bulge before McKinless denied O'Connor with a fantastic diving save only for the Mayo talisman to register his seventh point from a sweetly-struck '45'.
Loughlin replied from a free as Derry moved back ahead on 51 minutes and the lead was two with twelve minutes left as substitute James Kielt lofted over an easy free, 0-12 to 0-10. Wing back Patrick Durcan finally got Mayo back on the scoreboard with three minutes left and the westerners soared ahead when substitute Conor Loftus blasted the ball to the net in the 69th minute and then followed up with a terrific point - 1-12 to 0-12.
Incredibly, the Derry men drew level when substitute Mark Lynch rose highest to fist to the net in injury time, a score which ultimately meant that extra time would be required.
McLoughlin struck first in extra time and O'Connor's eighth of the day came from a free before another dreadful McKinless restart gifted Jason Doherty the sealing goal on 74 minutes. O'Connor thumped one over from play to make it 2-15 to 1-12 after 75 minutes.
Lynch pulled one back and Derry were handed a lifeline in the 77th minute when Chris Barrett conceded a penalty, but Clarke got down well to save Kielt's spot-kick. Durcan was dismissed before half time in extra time and O'Connor's free followed by an Aidan O'Shea point made it 2-17 to 1-13 with one ten-minute period left.
The winners added four unanswered points from there to the finish, while Keegan had to depart the action after picking up an injury late on.
Mayo - D Clarke; B Harrison; G Cafferkey, C Barrett; C Boyle, L Keegan (0-1), P Durcan (0-1); D Vaughan, T Parsons; F Boland, A O'Shea (0-1), S Coen; K McLoughlin (0-1), C O'Connor (0-12, 9f, 1'45), A Moran (0-2). Subs: D O'Connor (0-1) for F Boland, S O'Shea for D Vaughan, J Doherty (1-1) for S Coen, C Loftus (1-1) for A Moran, D Drake for B Harrison, C Crowe for C Barrett, S Nally for L Keegan, D Kirby for K McLoughlin.
Derry - B McKinless; N Keenan, B Rogers, K McKaigue; M McEvoy, C McFaul, C McWilliams (0-1); C McKaigue, C McAtamney; D Heavron (0-1), R Bell (0-2), N Loughlin (0-6, 5f); E Lynn, D Tallon, B Heron (0-1). Subs: E McGuckin for C McAtamney (BC), M Lynch (1-1) for D Tallon, J Kielt (0-1f) for R Bell, S McGuigan for E Lynn, C Nevin for M McEvoy, N Forrester for C McFaul, G O'Neill for N Loughlin, C Doherty for B Heron.
Referee - M Deegan.