Provide Menu in Module
You put the menu in the folder config/install of the module.

An example from the devel module:

/config/install/system.menu.devel.yml

id: devel
label: 'Development'
description: 'Links related to Devel module.'
langcode: en
locked: true


Then you can place the menu link items for this menu in *.links.menu.yml in the root directory of the module.

Edit:

As mentioned in the comment from @mradcliffe, some background info might be helpful. Menus are configuration entities. The storage of the configuration is for performance reasons in the database, but they were at the beginning of D8 in yaml files. If you sync the configuration to the harddisk you will find the configuration in a set of yaml files. You can put any of these yaml files in the config/install folder of your module. But you have to remove the uuid line, because the uuid is only valid for the installation you have exported the yaml file from. The menus are in system.menu.*.yml.