Jakob Silfverberg also scored in the shootout for Ottawa, while David Desharnais replied for Montreal.
After Regin gave the Senators the lead in the shootout, Bishop stopped Tomas Plekanec to secure Ottawa's season-high fifth straight win.
Regin had a chance to end the game late in overtime but his slapshot from the high slot hit the post behind Canadiens goaltender Carey Price, who finished with 23 saves.
Dave Dziurzynski had a goal in regulation for the Senators, while Andrei Markov scored for the Canadiens.
The teams were tied 1-1 after two periods and it stayed that way through the third and into overtime, which started 3-on-3 because of penalties.
Ottawa got one skater back and enjoyed a brief power play before Kyle Turris took a hooking penalty. It was back to a 3-on-3 before the Canadiens got their fourth power play of the game, but Montreal couldn't get the puck past Bishop.
Ottawa and Montreal played to a scoreless first period, although the Canadiens did have the best opportunity with Max Pacioretty hitting the post behind Bishop.
[to top of second column]
That was the beginning of the Canadiens' assault on goal posts. Erik Cole rang a shot off the crossbar in the second before Raphael Diaz hit the post to the right of Bishop.
Those two near misses came after Dziurzynski beat Price with a shot from the top of the faceoff circle that goalie should have had at 6:49.
The Canadiens finally solved Bishop with their 30th shot when Markov ripped a point shot on the power play with just 4 seconds remaining in the second.
NOTES: The Canadiens were in first place on Feb. 25 for the first time since 1993, the year they last won the Stanley Cup. ... Canadiens D Francis Bouillon played his 500th game with Montreal. He has played 695 total games in the NHL. ... Entering Monday's game Ottawa captain Daniel Alfredsson had 420 career goals. The rest of the Senators' lineup had a combined 524. ... After scoring four goals in his first four games, Senators F Kyle Turris has gone 16 games without a goal.
Copyright 2013 The Associated
Press. All rights reserved. This material may not be published,
broadcast, rewritten or redistributed.