The main federal murder statute, 18 USC 1111, applies only to murders committed in the special maritime and territorial jurisdiction of the United States. This consists of several different kinds of places and situations, and the authority of Congress to make criminal laws for each of them derive from different sections of the Constitution.
Let's go through them:
(1) The high seas, any other waters within the admiralty and maritime jurisdiction of the United States and out of the jurisdiction of any particular State, and any vessel belonging in whole or in part to the United States or any citizen thereof, or to any corporation created by or under the laws of the United States, or of any State, Territory, District, or possession thereof, when such vessel is within the admiralty and maritime jurisdiction of the United States and out of the jurisdiction of any particular State.
Article I, Section 8: "The Congress shall have Power [...] To define and punish Piracies and Felonies committed on the high Seas..."
(2) Any vessel registered, licensed, or enrolled under the laws of the United States, and being on a voyage upon the waters of any of the Great Lakes, or any of the waters connecting them, or upon the Saint Lawrence River where the same constitutes the International Boundary Line.
Maybe "high seas" again? Or "interstate commerce"? Not quite sure.
(3) Any lands reserved or acquired for the use of the United States, and under the exclusive or concurrent jurisdiction thereof, or any place purchased or otherwise acquired by the United States by consent of the legislature of the State in which the same shall be, for the erection of a fort, magazine, arsenal, dockyard, or other needful building.
Article I Section 8: "[...] to exercise like Authority over all Places purchased by the Consent of the Legislature of the State in which the Same shall be, for the Erection of Forts, Magazines, Arsenals, dock-Yards, and other needful Buildings;"
Article IV Section 3: "The Congress shall have Power to dispose of and make all needful Rules and Regulations respecting the Territory or other Property belonging to the United States"
(4) Any island, rock, or key containing deposits of guano, which may, at the discretion of the President, be considered as appertaining to the United States.
"Territory or other Property" and/or "high Seas".
(5) Any aircraft belonging in whole or in part to the United States, or any citizen thereof, or to any corporation created by or under the laws of the United States, or any State, Territory, district, or possession thereof, while such aircraft is in flight over the high seas, or over any other waters within the admiralty and maritime jurisdiction of the United States and out of the jurisdiction of any particular State.
Presumably a modern extension of "high seas".
(6) Any vehicle used or designed for flight or navigation in space and on the registry of the United States [...].
Ditto.
(7) Any place outside the jurisdiction of any nation with respect to an offense by or against a national of the United States.
Probably "high seas" again as this was the main historical example of "a place outside the jurisdiction of any nation".
(8) To the extent permitted by international law, any foreign vessel during a voyage having a scheduled departure from or arrival in the United States with respect to an offense committed by or against a national of the United States.
Not quite sure. Possibly "to regulate Commerce with foreign Nations".
(9) With respect to offenses committed by or against a national of the United States as that term is used in section 101 of the Immigration and Nationality Act— (A) the premises of United States diplomatic, consular, military or other United States Government missions or entities in foreign States, including the buildings, parts of buildings, and land appurtenant or ancillary thereto or used for purposes of those missions or entities, irrespective of ownership; and (B) residences in foreign States and the land appurtenant or ancillary thereto, irrespective of ownership, used for purposes of those missions or entities or used by United States personnel assigned to those missions or entities.
"Territory and other Property" again.