Karlsson and Kovalev scored nine seconds apart in the first period to break the previous team record by one second. Karlsson opened the scoring with a power-play goal 5:27 in. His goal was still being announced when Kovalev made it 2-0 at 5:36, breaking a modern franchise record set 15 years earlier.
"I don't usually think of those things," Kovalev said. "Maybe for you guys to remind [me] it makes me feel better for the rest of the day. It's always nice to be part of history."
Martin Straka and Antii Tormanen scored 10 seconds apart in the second period of a 4-2 win over Calgary at the Ottawa Civic Centre on Oct. 19, 1995.
Gonchar, who became the sixth Russian player to reach the 1,000-game milestone, assisted on Daniel Alfredsson's goal during a two-man advantage late in the period.
"It's not about the point, it's mostly about the win," Gonchar said. "We haven't played well lately and you get a win and there's a great atmosphere in the locker room after the game. That's more important than the point."
Kovalev also assisted on the goal for his third point of the night.
"It's always important to contribute, not just to have 1,000 games, but to be a part of the 1,000th game," Kovalev said. "He was trying to score on that 5-on-3. He missed the net a couple of times but we did pretty good for him. He got the point and we won the game -- something to be remembered."
Jason LaBarbera made 17 saves in the first during his second start of the season. Ilya Bryzgalov, who made 26 saves in a 3-2 overtime loss in Montreal, replaced LaBarbera to start the second. He stopped 14 shots in two periods.
Coyotes captain Shane Doan was back in the lineup after serving a three-game suspension for his blindside hit on Anaheim's Dan Sexton on Oct. 17.
"We put ourselves in the position where we have to chase a game the whole night and gave them the opportunity to feel good about themselves," Doan said.
Outshot 20-8 while falling behind 3-0 in the first, Phoenix held an 11-5 margin in shots in the second.
Lepisto scored his first of the season 4:15 into the middle period and Yandle drew the Coyotes within 3-2 with his first goal at 6:58 of the third.
Kovalev restored Ottawa's two-goal lead 48 seconds later when he beat Bryzgalov.
Karlsson put Mike Fisher's rebound into the right side with Doan off for slashing. Kovalev then got his first of the season.
"Tonight it was really important to take the lead," Kovalev said. "I'm glad we took that lead right from the start and we got a quick couple of goals."
Nick Foligno, who assisted on Kovalev's first goal, put a backhand off the left post midway through the first before Kelly made it 3-0 with his second of the season at 14:45.
- LaBarbera's only other appearance this season was a 32-save effort in a 3-2 loss in Anaheim on Oct. 17.
- Gonchar received his NHL milestone award from Jim Gregory, the league's senior vice president of hockey operations, in a pregame ceremony. The veteran Russian defenseman has 688 points, including 202 goals, with Washington, Boston, Pittsburgh and Ottawa.