This is definitely an old question, but was frustrating me too and none of the other answers changed the legend title fontsize at all, but instead just changed the rest of the text. So after banging my head against the matplotlib documentation for awhile I came up with this.
legend = ax1.legend(loc=0, ncol=1, bbox_to_anchor=(0, 0, 1, 1),
prop = fontP,fancybox=True,shadow=False,title="LEGEND")
plt.setp(legend.get_title(),fontsize="xx-small")
As of Matplotlib 3.0.3, you can also set it globally with
plt.rcParams['legend.title_fontsize'] = 'xx-small'