When did the books of Tanakh get their canonical names? I understand that Five Books of the Torah were named after the first words in them, and that most of Navi was named after their authors, but when did some of the less obvious ones (such as Shmuel, Divrei Hayamim, Melakhim, Shoftim, Shir HaShirim, Esther, Ruth, and Trei Asar) get their names?
I have no source for the following claims, so please consider this like an extended comment more than an official answer.
Today when people write books, they choose titles for them, which are printed on the title page before the text. In biblical times, I doubt this was the case. Still, though, a title is necessary for when people refer to the book in writing or in conversation. (e.g. "Hey Mark, have you read...?) Because of this, I assume that people came up with titles for the books which became widespread and over time one particular name became the accepted one. [Consider, for example, "The Declaration of Independence", which I don't think is formally titled as such. But people began to call it that and it became accepted; or maybe someone famous referred to it as such, and it stuck.]
By the time Chazal (traditionally, Anshei K'nesses HaG'dolah) came around and canonized the Tanach, it seems names were already well-known. Bava Basra 14b:
ת"ר סדרן של נביאים יהושע ושופטים שמואל ומלכים ירמיה ויחזקאל ישעיה ושנים עשר סידרן של כתובים רות וספר תהלים ואיוב ומשלי קהלת שיר השירים וקינות דניאל ומגילת אסתר עזרא ודברי הימים
The b'raisa presents the order as if everyone should know what book it refers to when it says e.g. "Melachim".
It remains to be determined why each book was given its particular name, or why the name it has became the "accepted" name. First, though, note that each section of Tanach also have given names (Torah, Neviim, K'suvim). These names are clearly only as old as the canonization of Tanach, since there is no reason to assume that the books were thus organized beforehand. Therefore, we find Abarbanel introducing his commentary on the Prophets with the following:
המחקר הראשון בחלוקת ספרי הקדש בכלל, הנה חכמינו הקדושים ז׳׳ל חלקו ספרי הקדש חלוקה ראשונה לשלשה חלקים, ויקראו אותם תורה נביאים וכתובים, וראוי שנדע למה נקראו בשמות האלה ומהו ההבדל העצמי אשר ביניהם שיורו עליו שמותיהם
For the names of the individual books, some cases are more obvious than others. The books of the Torah, for example, are clearly called by the first (determining) word(s) of the book. Bereshis, Shemos, Vayikra, Bamidbar, Devarim. This seems the be the case for other books as well. Consider Shir HaShirim, Mishlei, Koheles, and Eichah. (Although, notice that in Bava Basra, Eicha is called "Kinnos", likely inspired by II Chronicles 35:25.) The first three (Shir HaShirim, Mishlei, Koheles) all have "title sentences" at the beginning, which is probably why they are called what they are called. In fact, perhaps it was common at the time of their composition to name books like that, introducing the title in the first line of the text.
Other books are named for the main character of interest. For books of prophecies, the name always belongs to the prophet. Yeshayahu, Yirmiyahu, Yechezkel, Hoshea, Yoel, Amos, Ovadia, Yonah, Micha, Nachum, Chabakuk, Tzefania, Chagai, Zecharia, Malachi. I included the books of Trei Asar as their own titles, as once again, the compilation into one book is likely the effect of Anshei K'nesses HaG'dola's canonization, with the individual names probably being the ones that existed before that. Other books that are named for their main characters: Yehoshua, Shmuel, Ruth, Iyov, Daniel, Ezra, Esther. (With regard to Esther, I don't know if I would say she is the main character in the story, but certainly she is of the most pivotal characters.)
Lastly, the books that are not really historical or don't really have a "main character of the story" are named for their content and overall theme. Shoftim, Melachim, Tehillim, Divrei Hayamim. Shoftim and Melachim seem pretty clear to me and Divrei Hayamim even clearer. It is Tehillim that requires a little thought. It is referred to as "Sefer Tehillim" in Bava Basra, although maybe the original text is "Tehillos", since both Ibn Ezra and Seforno begin their commentaries with "...זה ספר תהלות". If I were naming the books, I probably would have gone with "Sefer Mizmorim", but it is true that תהלה is a central theme in Tehillim (e.g. "וּפִי יַגִּיד תְּהִלָּתֶךָ", "יִמָּלֵא פִי תְּהִלָּתֶךָ", "כְּשִׁמְךָ אֱלֹהִים כֵּן תְּהִלָּתְךָ") as well as the ending note of the book ("כֹּל הַנְּשָׁמָה תְּהַלֵּל יָהּ הַלְלוּ יָהּ").