Я мог бы создать две разные легенды, используя метод add_artist
(в противном случае он просто заменит предыдущую легенду), который позволит вам установить их обе в разные места, например:
from matplotlib.lines import Line2D
custom_lines = [Line2D([0], [0], color=cmap(0.), lw=4),
Line2D([0], [0], color=cmap(.5), lw=4),
Line2D([0], [0], color=cmap(1.), lw=4)]
fig, ax = plt.subplots()
lines = ax.plot(data)
legend1 = plt.legend(custom_lines[1:], ['Medium', 'Hot'])
legend2 = plt.legend(custom_lines[0], 'Cold', loc=10)
ax.add_artist(legend1)
ax.add_artist(legend2)