Your question is essentially broken into four parts.
1) What is the origin of this prayer?
2) Where is it usually inscribed?
3) What accounts for the two types of praise (שבח and תהלה) used in the inscription?
4) Why is G-d's name (אל שדי) used as opposed to other names?
First it should noted that this is not a prayer in the sense of a request to G-d. It is more like a statement of praise.
As you point out, תושלב״ע is a Notarikon formed from the first letters of the phrase, תם ונשלם שבח לאל (שדי) בורא עולם.
As to its origin, if you mean its first usage, as far as I know, this is impossible to determine. It has been used to mark the completion of Jewish texts for at least 1000 years, but is likely much older.
There are sometimes slight variations from one author or another (like noted at this link) in regard to intended meaning. But the most common formats are תושלב״ע or תותלב״ע as you noted in your question. The second form stands for: תם ונשלמת תהלה לאל בורא עולם.
The inscription is not mandatory, but when it is used, it usually is placed at the end of books. This is in keeping with the meaning of the phrase it represents.
It is written by the author when they complete a book and is intended to parallel G-d's act of completing creation, which is the root and source of all acts of completion. This is in keeping with the teaching of Rabbi Dov Ber, the Maggid of Mezerich in Maggid D'varav l'Yaakov 50:1 which says:
אין דבר למטה שאין לו שרש למעלה כידוע אין לך עשב וכו' ושורש כל השרשים הוא רצון הקדמון שעלה ברצונו לברוא את העולמות
In order to address your question about the two types of praise mentioned, it requires first understanding the meaning of the opening words, תם ונשלם.
תם is from the verb root תמם and means to make (or to be made) whole. This follows the explanation of the word by Rabbi Aharon Kotler, z"l in his introduction to Sefer Orot HaGra, paragraph 4 on the posuk from Tehillim 19:8 where he says:
תורת ה׳ תמימה משיבת נפש, אימתי משיבת נפש כשהיא תמימה כו׳ וחלק הנסתר שבתורה וסודות הדברים מתאימות עם הפשט וההלכה וכולם כקומה שלמה אחת כו׳ וכן הוא בכל חלקי פרד״ס (פשט, רמז, דרוש וסוד) כו׳ וכמו כן נצפנו כל סודות העולמות, מה שהיה והוה ומה שעתיד להיות. (היינו כל עולם הזה וגם כל עולם הבא) .כו׳
The binyan of תם is kal and in the first person. It can be either past tense (a completed action) or present (continuous) tense. In the context of a book author, it would be understood in past tense, that the author completed the book. But in the context of the conclusion of the phrase (בורא עולם), it means continuously being made whole. This follows the same format as found in the Yotzer blessing said before morning Shema, how G-d continuously creates and forms all of creation every moment.
Another point to mention from the end of the quote from Rabbi Kotler is that the word תם also suggests an alternate meaning to the notarikon
תושלב״ע. It also has a meaning of תו שלבי עולם. There are two stages to the creation of the universe. (In keeping with Sefer Yetzirah 2:3, the letter Tav of תו is exchangeable with the letter Dalet.) And this principle about the two stages is in keeping with what Rashi explains to Bereshit 2:4.
נשלם is from the root שלם meaning complete or perfect and is in the binyan nifal (passive/reflexive).
The change in binyan between תם and נשלם indicates the one doing the action (תם) and the effect upon the receiver of the action (נשלם). That G-d is continuously making the creation whole and as a consequence, the creation is complete or perfect.
With this understanding it is now possible to explain the variations used in the types of praise.
שבח is referring to the Shechinah, G-d's revealed presence, like is explained in Sefer Kehillat Yaacov by Rabbi Yaacov Tzvi Yolles, ערך שבח.
There are two aspects of Shechinah discussed in the Torah, Upper level Shechinah which is associated with the Heavenly realm (the aspect Malchut as it relates to Binah) and lower level Shechinah which is associated with this physical, material world (the aspect of Malchut), as explained in Sefer Kehillat Yaacov, ערך שכינה.
Malchut, in general, is the completion of all Sefirot and is a vessel to receive the influence of all the Sefirot above it.
תהלה is associated with this upper level aspect of Shechinah like is explained in Sefer Kehillat Yaacov, ערך תהלה.
And this explains why there are these two forms of praise used in this expression.
And this leads to the 4th and final part of your question, namely why does it use this particular name of G-d?
This concept is discussed in Chagigah 12a in the name of Reish Lakish which explains that the name El Shaddai is the name associated with completing each act of creation. Like it says:
ואמר רב יהודה אמר רב בשעה שברא הקב"ה את העולם היה מרחיב והולך כשתי פקעיות של שתי עד שגער בו הקב"ה והעמידו שנאמר עמודי שמים ירופפו ויתמהו מגערתו והיינו דאמר ר"ל מאי דכתיב (בראשית לה, יא) אני אל שדי אני הוא שאמרתי לעולם די אמר ר"ל בשעה שברא הקב"ה את הים היה מרחיב והולך עד שגער בו הקב"ה ויבשו שנאמר (נחום א, ד) גוער בים ויבשהו וכל הנהרות החריב
Reish Lakish said: What is the meaning of that which is written: “I am the Almighty God [El Shaddai]” (Genesis 17:1)? It means: I am He Who said to the world “enough [dai],” instructing it to stop expanding.
It might seem curious that G-d would need to tell the process of creation and formation, which is associated with other names of G-d mentioned in parshat Bereshit, to stop. But if one considers what unrestricted and uncontrolled formation means in regard to living things, it is more obvious. Cancer is, in general, the unrestricted and uncontrolled formation of cells. A consequence, so to speak, of the absence of that limit.