You want to add legend without the axes size being reduced? Easy, just add the legend inside the axes, e.g. southwest, as this won't change the axes size. Then change its position property to move it outside of the plot. I always recommend using the tight_subplot function from fileexchange to make subplots, especially when you are writing a paper and need to minimize empty space. It also let's you set the right margin so that you can fit the legend.
Example
figure;
set(gcf,'units','centimeters','position',[10 10 12 6])
[ha pos]=tight_subplot(1,2,0.05,[0.1 0.05],[0.05 0.2])
axes(ha(1))
h=plot([1 2;2 1;3 1]',[1 2;3 1; 4 5]')
axes(ha(2))
h=plot([1 2;2 1;3 1]',[1 2;3 1; 4 5]')
lh=legend(h,'location','east')
set(lh,'position',[.85 .5 .1 .1])
Image attached