A fine old book with many 'songs' (as pointed out by Gargoyle, our concept of song is quite different from that of conservative American Indians) is
"The Indians' Book," recorded and edited by Natalie Curtis, first issued in 1905. This work, with some 200 song-poems along with tales, myths and art, has been beautifully reprinted by Bonanza Books and is a first reference for one interested in the subject. Curtis carefully transliterated the songs she collected, and arranged them into our system of rhythm and melody. The third element, harmony, is lacking.
Different Indian groups vary widely in their songs and manner of singing.

The Navajo Language doesn't have a word for tune; the meaning is bound into the particular kind of song and its essential elements.
These essential elements are called the sin bikétl*'ool, sin bá siláii (*HTML doesn't have the symbol for this letter).