If Whitman were in a relationship with "titles" for "Song of Myself" on Facebook, the status would read, "It's complicated." In the first, historic edition of Leaves of Grass from 1855, the poem has no title. The collection has a lengthy and famous preface in prose (which you should read – check it out here), in which Whitman explains his ideas of poetry and democracy. Then he just launches right into the poem. People who read that first edition probably assumed the title of the poem was "Leaves of Grass."
And yes, "Leaves of Grass" would be an appropriate title, because one of the poem's central images is grass. Specifically, Whitman thinks that grass is a symbol of hope but also of the dead people who are buried beneath it and try to communicate to the living.
Leaves of Grass is also a famous pun. A "leaf" can be both the green thing that hangs from trees and also a page in a book. So Whitman wants you to think that, literally, the book you hold in your hands is like a clump of grass. Also, we don't normally think of grass as having leaves. Grass has blades; trees have leaves. The speaker, however, compares this small plant (i.e., grass) to larger trees. In Whitman's world, small things can be huge.
In the second edition of Leaves of Grass, published in 1856, Whitman added the title, "Poem of Walt Whitman, an American." This title reminds us of Section 24 of the poem, in which he describes himself as "Walt Whitman, an American, one of the roughs, a kosmos." So far as we know, no other poet up to this point had ever titled their longest poem with their own name.
In 1860, Whitman shortened the title to "Song of Myself." This change is important because we suspect that "Walt Whitman" and "Myself" (or "Me Myself") might actually be different "characters" in the poem. This final title is also more democratic, and focuses our attention of the "Me Myself" persona. Anyone could write a poem called "Song of Myself." This one just happens to be written by Whitman.
A "song," by the way, is both a piece of music and an old-fashioned word for "poem." Songs are meant to be performed, and this poem is a grand performance to be sure.