Indians starter Justin Masterson gave up Cincinnati's first five runs on four hits over four innings, walking two and striking out six.
"First of all, I thought it was his best stuff of the spring by far," Indians manager Terry Francona said. "Velocity. Life on the ball. He left a couple up that, kind of like Cody [Allen] did [in the seventh], went a long way. The good side of it was he settled back in and started getting the ball down.
"And when it was down where he wanted it to be, it had tremendous sink and movement. In this game, hitters will kind of show you that you better throw it where you want to."
Paul hit a 2-2 pitch to center field for a three-run homer, his second long ball of spring, following back-to-back singles by Zack Cosart and Joey Votto. Jay Bruce followed with a walk before Frazier hit his second homer of the spring with a two-run shot to left field that made it a 5-0 game.
Reds starter Mat Latos pitched five innings and allowed three runs (two earned) on six hits with no walks and three strikeouts. Latos, who had struggled in the early going of his earlier outings, retired six of the first seven batters he faced, allowing only a Matt Carson single in the second inning.
Luis Hernandez led off the third with a single before Brian Jeroloman reached on first baseman a fielding error by Votto. After Michael Bourn grounded into a double play, Hernandez scored on Drew Stubbs' infield hit to shortstop.
The Indians scored twice in the fourth on an RBI double by Chris McGuiness that brought home Cord Phelps and a Juan Diaz groundout to shortstop that plated Carson. Diaz added another run in the sixth with a sacrifice fly against Pedro Villarreal.
Cincinnati padded its lead with back-to-back homers in the seventh from Chris Heisey and Dennis Phipps against reliever Cody Allen before the Indians launched their rally in the ninth.
Up next for the Indians: Ubaldo Jimenez, who is lined up to be the Tribe's No. 2 starter this season, is scheduled to log six innings Monday, when the Indians host the Brewers in a 4:05 p.m. ET Cactus League contest at Goodyear Ballpark. Milwaukee will counter with right-hander Marco Estrada. Relievers Scott Barnes, Joe Smith and Nick Hagadone are also slated to pitch for Cleveland. The game will be available on MLB.TV or an exclusive webcast on indians.com.
Mark Sheldon is a reporter for MLB.com. Read his blog, Mark My Word, and follow him on Twitter @m_sheldon. This story was not subject to the approval of Major League Baseball or its clubs.