Deleting nodes did not remove the node-related menus
These Q/A may be helpful for you:
Delete all nodes of a given content type
How to bulk delete content of a given type?
According to the first Q/A, the Delete all module is worth to try.

You could also try mass delete node. The function node_delete() is safe to call. It has a call to node_delete_multiple() which deletes all related components of a node, such as entities, files, revisions, history, etc.

[UPDATE]
If you already deleted your nodes, but node-related menus are still there, you could also try out menu_rebuild() to rebuild your navigation menus. Check this answer. You could also add menu_rebuild() at the end of the script of mass delete node I mentioned above.

OR

If you know menu IDs, you can remove each of them using menu_link_delete().