How to show shapefile label in python basemap legend?

The idea to create a legend entry would be to draw the shapes as polygons, which can then be added to the legend.
Therfore we would first deactivate drawbounds, m.readshapefile(fn, 'shf', drawbounds = False). We can then create a matplotlib.patches.Polygon from the shapefile and add it to the axes, plt.gca().add_artist(polygon).

The legend can then be updated using this polygon

handles, labels = plt.gca().get_legend_handles_labels()
handles.extend([polygon])  
labels.extend(["Name of the shape"])                     
plt.legend(handles=handles, labels=labels)

Here is now some code in action, which produces the following images. It uses the ne_10m_admin_0_countries file.

from mpl_toolkits.basemap import Basemap
import matplotlib.pyplot as plt
from matplotlib.patches import Polygon
import numpy as np

m = Basemap(llcrnrlon=-10,llcrnrlat=35,urcrnrlon=35,urcrnrlat=60.,
             resolution='i', projection='tmerc', lat_0 = 48.9, lon_0 = 15.3)

m.drawcoastlines()
m.drawcountries(zorder=0, color=(.9,.9,.9), linewidth=1)

fn = r"ne_10m_admin_0_countries\ne_10m_admin_0_countries"
m.readshapefile(fn, 'shf', drawbounds = False)

#Madrid
x,y = m([-3.703889],[40.4125])
m.plot(x,y, marker="o", color="blue", label="Madrid", ls="")

# some countries
countries = ['Switzerland', 'Ireland', "Belgium"]
colors= {'Switzerland':"red", 'Ireland':"orange", 'Belgium' : "purple"}
shapes = {}
for info, shape in zip(m.shf_info, m.shf):
    if info['NAME'] in countries:
        p= Polygon(np.array(shape), True, facecolor= colors[info['NAME']], 
                   edgecolor='none', alpha=0.7, zorder=2)
        shapes.update({info['NAME'] : p})

for country in countries:
    plt.gca().add_artist(shapes[country]) 


# create legend, by first getting the already present handles, labels
handles, labels = plt.gca().get_legend_handles_labels()
# and then adding the new ones
handles.extend([shapes[c] for c in countries])  
labels.extend(countries)                     
plt.legend(handles=handles, labels=labels, framealpha=1.)

plt.show()

Now because we already have a polygon with the shape, why not make the legend a bit more fancy, by directly plotting the shape into the legend. This can be done as follows.

from mpl_toolkits.basemap import Basemap
import matplotlib.pyplot as plt
from matplotlib.patches import Polygon
import numpy as np

m = Basemap(llcrnrlon=-10,llcrnrlat=35,urcrnrlon=35,urcrnrlat=60.,
             resolution='i', projection='tmerc', lat_0 = 48.9, lon_0 = 15.3)

m.drawcoastlines()

fn = r"ne_10m_admin_0_countries\ne_10m_admin_0_countries"
m.readshapefile(fn, 'shf', drawbounds = False)

#Madrid
x,y = m([-3.703889],[40.4125])
m.plot(x,y, marker="o", color="blue", label="Madrid", ls="")

countries = ['Switzerland', 'Ireland', "Belgium"]
colors= {'Switzerland':"red", 'Ireland':"orange", 'Belgium' : "purple"}
shapes = {}
for info, shape in zip(m.shf_info, m.shf):
    if info['NAME'] in countries:
        p= Polygon(np.array(shape), True, facecolor= colors[info['NAME']], 
                   edgecolor='none', alpha=0.7, zorder=2)
        shapes.update({info['NAME'] : p})

for country in countries:
    plt.gca().add_artist(shapes[country]) 


class PolygonN(object):
    def legend_artist(self, legend, orig_handle, fontsize, handlebox):
        x0, y0 = handlebox.xdescent, handlebox.ydescent
        width, height = handlebox.width, handlebox.height
        aspect= height/float(width)
        verts = orig_handle.get_xy()
        minx, miny = verts[:,0].min(), verts[:,1].min()
        maxx, maxy = verts[:,0].max(), verts[:,1].max()
        aspect= (maxy-miny)/float((maxx-minx))
        nvx = (verts[:,0]-minx)*float(height)/aspect/(maxx-minx)-x0
        nvy = (verts[:,1]-miny)*float(height)/(maxy-miny)-y0

        p = Polygon(np.c_[nvx, nvy])
        p.update_from(orig_handle)
        p.set_transform(handlebox.get_transform())

        handlebox.add_artist(p)
        return p

handles, labels = plt.gca().get_legend_handles_labels()
handles.extend([shapes[c] for c in countries])  
labels.extend(countries)     
plt.legend(handles=handles, labels=labels, handleheight=3, handlelength=3, framealpha=1.,
           handler_map={Polygon: PolygonN()} )

plt.show()