I wasn't able to find an elegant solution to your question, but have an idea how to do this with some tricks.
Method 1
The obvious choice is to make a legend with 3 columns. If we assume that the legend is a table, then we need a header - first line where we add a column names. Legend is filled with patches column by column, not row by row. In order to handle that behavior we are going to create a three separate lists for each legend's column and add patches to them. Then join all three lists and add the final list of patches to the legend.
As the result you should get a legend like this one:

The code to generate that image is below
from random import random
import matplotlib.patches as m_patches
import matplotlib.pyplot as plt
groups = [{'Type 1': [i+random() for _ in range(25)], 'Type 2': [i+random() for _ in range(25)]} for i in range(10)]
markers = ['o', 'v', '^', '<', '>', '8', 's', 'p', '*', 'h']
colors = ['r', 'g', 'b', 'salmon', 'lime', 'purple', 'cyan', 'gold', 'peru', 'gray']
def main():
# Make legend with 3 columns:
# First column for group number, seconds on for Type 1 lines, and third for Type 2 lines
n_cols = 3
# Figure size
fig_width = 13
fig_height = 7
# Axis location
# Note that width must be lower than 1 so we could add legend to the right from a plot
ax_left, ax_bottom = 0.1, 0.1
ax_width, ax_height = 0.6, 0.8
# Make a figure
plt.figure(figsize=(fig_width, fig_height))
# Create axes
ax = plt.axes([ax_left, ax_bottom, ax_width, ax_height])
# Since we are going to create a custom legend, create a list of patches for each column
patches_column1 = [m_patches.Patch(color="w", label=f'')]
patches_column2 = [m_patches.Patch(color="none", label=f'Type 1')]
patches_column3 = [m_patches.Patch(color="none", label=f'Type 2')]
for i, (group, color, marker) in enumerate(zip(groups, colors, markers)):
l1, = ax.plot(group['Type 1'], f"{marker}-", color=color, label=f"Fill")
l2, = ax.plot(group['Type 2'], f"{marker}-", color=color, label=f"Empty", markerfacecolor='none')
# First column contains a 'group' info patch
patches_column1.append(m_patches.Patch(color='none', label=f'Group {i}'))
# Second column contains patches with lines of Type 1
patches_column2.append(l1)
# Third column contains patches with lines of Type 2
patches_column3.append(l2)
# Now we need to merge all three lists together and add the final list to a legend
patches = list()
patches.extend(patches_column1)
patches.extend(patches_column2)
patches.extend(patches_column3)
ax.legend(loc='upper left',
bbox_to_anchor=(1.0, 0.0, 1, 1),
ncol=n_cols, handles=patches)
plt.savefig("fig1", dpi=200, facecolor='w', edgecolor='w',
orientation='portrait', papertype=None, format=None,
transparent=False, bbox_inches=None, pad_inches=0.1,
frameon=None, metadata=None)
plt.show()
if __name__ == '__main__':
main()
However you will have Fill and Empty labels on the legend. I wasn't able to find an simple way to remove them, but found an ugly one.
Method 2
This is the same as method 1 except now we are going to make some manipulations with markers and text on a legend.
First we need to add one additional parameter to a legend() constructor:
handletextpad=-2.5. This parameter will shift the marker and place it approximately in the middle of a column. Now we need to hide a text that corresponds to each line marker ('Fill' and 'Empty'). In order to do that we are going to get all the text objects from the legend and update its color to a 'black' or 'none' depending on what we want to hide. As the result you should get something like this:

The complete code is below
from random import random
import matplotlib.patches as m_patches
import matplotlib.pyplot as plt
groups = [{'Type 1': [i+random() for _ in range(25)], 'Type 2': [i+random() for _ in range(25)]} for i in range(10)]
markers = ['o', 'v', '^', '<', '>', '8', 's', 'p', '*', 'h']
colors = ['r', 'g', 'b', 'salmon', 'lime', 'purple', 'cyan', 'gold', 'peru', 'gray']
def main():
# Make legend with 3 columns:
# First column for group number, seconds on for Type 1 lines, and third for Type 2 lines
n_cols = 3
# Figure size
fig_width = 10
fig_height = 7
# Axis location
# Note that width must be lower than 1 so we could add legend to the right from a plot
ax_left, ax_bottom = 0.1, 0.1
ax_width, ax_height = 0.65, 0.8
# Make a figure
plt.figure(figsize=(fig_width, fig_height))
# Create axes
ax = plt.axes([ax_left, ax_bottom, ax_width, ax_height])
# Since we are going to create a custom legend, create a list of patches for each column
patches_column1 = [m_patches.Patch(color="w", label=f'')]
patches_column2 = [m_patches.Patch(color="none", label=f'Type 1')]
patches_column3 = [m_patches.Patch(color="none", label=f'Type 2')]
for i, (group, color, marker) in enumerate(zip(groups, colors, markers)):
l1, = ax.plot(group['Type 1'], f"{marker}-", color=color, label="Filled")
l2, = ax.plot(group['Type 2'], f"{marker}-", color=color, markerfacecolor='none', label="Empty")
# First column contains a 'group' info patch
patches_column1.append(m_patches.Patch(color='none', label=f'Group {i}'))
# Second column contains patches with lines of Type 1
patches_column2.append(l1)
# Third column contains patches with lines of Type 2
patches_column3.append(l2)
# Now we need to merge all three lists together and add the final list to a legend
patches = list()
patches.extend(patches_column1)
patches.extend(patches_column2)
patches.extend(patches_column3)
# If you plan to
lg = ax.legend(loc='upper left',
bbox_to_anchor=(1.0, 0.0, 1, 1),
ncol=n_cols,
handles=patches,
handletextpad=-2.5,
borderpad=1.0)
for i, text in enumerate(lg.get_texts()):
if i < 11:
pass
elif i == 11:
text.set_color('black')
elif 12 <= i < 22:
text.set_color('none')
elif i == 22:
text.set_color('black')
else:
text.set_color('none')
plt.savefig("fig2", dpi=200, facecolor='w', edgecolor='w',
orientation='portrait', papertype=None, format=None,
transparent=False, bbox_inches=None, pad_inches=0.1,
frameon=None, metadata=None)
plt.show()
if __name__ == '__main__':
main()