First - the House that votes is the House elected in 1858-59.
Second - it doesn't matter whether Republicans have a majority of Representatives; the House votes by state delegations. A majority of the 33 delegations is required to elect.
Republicans control 15 delegations (all free states except IL, CA, OR). Douglas Democrats control 1 delegation (IL, 5-4). Breckinridge Democrats control IIRC 13 (CA, OR, DE, and 10 Upper and Deep South states). KY is controlled by the "Opposition" group (i.e. ex-Whigs, now presumably supporting "Constitutional Union" candidate Bell). TN and IIRC MD are split between Breckinridge Democrats and Oppositionists or Know-Nothings. MO is split three or four ways.
One other point: Before the vote, Douglas stated that he would not accept election by the House. OTL, he was fourth in EV, so not eligible. If Douglas wins NY, that gives him 47 EV to 39 for Bell, so he's in and Bell's out. But he's put himself out.
Most likely, the Oppositionists (who were from slave states anyway) fall into line behind Breckinridge, which would give him 17 states.
One other possibility is interesting: the Vice President is elected by the Senate (voting individually); only the top two EV finishers are eligible, i.e. Lincoln's running mate Hamlin, and Breckinridge's running mate, Sen. Joe Lane of OR. The Senate is overwhelmingly Democrat, so it will be Lane. If the House deadlocks, Lane becomes President. And in fact, during the campaign Republicans harped on this, asserting that the choice was "Lincoln or Lane". (A minor point in this was that OR's sole Representative was a Lane crony. By abstaining, or voting for Douglas, he could deadlock the House and thus put his buddy in the White House.)
One other possibility: one of the Douglas Democrats from IL is so angry at the Breckinridge Democrats that he votes for Lincoln, giving him 16 states; and the Republicans bribe or bully one of the sole Representatives from OR or DE to vote for Lincoln. They're both Breckinridge Democrats, but the Republicans could apply enormous pressure for such a great prize, and after all Lincoln did lead in popular votes.