It looks like the etymology of titulus is unclear. The Lewis and Short suggestion that it is related to τίνω seems a bit hard to accept (unless titulus was borrowed at some point from some Greek form), as Wiktionary indicates that the initial consonant of τίνω is thought to have come from a PIE labiovelar *kʷ. The change of *kʷ to /t/ before /i/ is specific to certain dialects of Greek; we wouldn't see it in a native Latin word (compare Latin quis vs. Attic Greek τίς).
Etruscan?
Wiktionary says "Most likely from Etruscan", citing Ostler, Ad Infinitum: A Biography of Latin (2007), p. 43.
The form at least seems to be consistent with an Etruscan origin, since the phonemes /t/, /i/, /u/ and /l/ all existed in Etruscan. But the suggestion that titulus is Etruscan seems to be based on rather slim evidence. Ostler describes his Appendix II ("Etruscan Borrowings in Latin") as a "liberal list, supplementing the list of clearly attested borrowings on the assumption that early words that have no Italic etymology are likely to be Etruscan, especially if they have recognizable Etruscan word endings (-eus, -enna, -erna, -īna, -issa, -ō, -ulus, -urnum)", and notes that "hardly any of these words can be identified in Etruscan texts" (p. 323).
Ostler cites Ernout 1930 as a source that describes supposedly characteristic features of "Etruscan Latin", such as the list of endings that Ostler gives (Ad Infinitum, p. 334). I have found some later literature that critiques some of Ernout's criteria (Giuliano Bonfante, 1985, "Etruscan Words in Latin"), but Bonfante doesn't seem to discuss titulus or any other words ending in -ulus.
-ulus as an Etruscan word ending?
Here are some of the other -ulus words from Ostler's Appendix II:
- catulus 'puppy', botulus* 'black pudding', mitulus [sic]† 'mussel', situlus 'basket', populus 'people', tutulus 'priest's cap'
I don't see a clear meaning associated with the alleged Etruscan ending -ulus. (Ostler's list also includes words ending in -ula, which I haven't reproduced here.)
*According to Bonfante, borrowings from Etruscan should not be expected to have /b/, or any other voiced plosive. Ostler doesn't seem to have used this criterion when compiling his list.
†The actual form seems to have been mītŭlus, with a long vowel in the first syllable. Lewis and Short indicate that it is in some way from Greek μύτυλος. (A Greek origin doesn't exclude the possibility of Etruscan as an intermediate source of the word.)
Indo-European?
There seems to be no obvious candidate for an Indo-European etymon. András Cser points out that CiVCi, with the same consonant before and after the vowel, is an uncharacteristic pattern for the start of a PIE root, and says that according to Walde and Hoffmann (1956 s.v.), the form titulus might be the result of reduplication (p.181, "Aspects of the Phonology and
Morphology of Classical Latin", 2016).
Stilus?
The suggestion that luchonacho found of a relationship between titulus and stilus seemed intriguing to me, so I wanted to add some comments about that (without trying to copy luchonacho's answer, or take credit for finding Kennedy's article).
The word stilus actually also seems to have a somewhat unclear/disputed etymology. The suggestion that it is related to titulus seems to rely largely on the phenomenon of so-called "s mobile", which affects Indo-European roots.
But it's not obvious whether stilus is based on an Indo-European root.
Wiktionary and Lewis and Short both suggest that stilus is related to Greek στίζω.
De Vaan says "it is uncertain whether Latin stilus, stimulus and stīva all belong together, but one might see a root sti- 'sharp object' in them. It has been argued that they contain the core of the root *stig- 'to sting' (see s.v. stinguō), the -g- of which would be a root enlargement; although this is not completely impossible, there are no positive indications in this direction. Another possible cognate might be Av. staēra-, taēra- [m.] 'mountain-top' < *(s)te/oir/lo-, if to stilus. But since the root cannot be determined, this etymology remains gratuitous."
Ostler says stilus "has no etymology and has also been proposed as a loan from Etruscan" (p. 43; he cites a source that I unfortunately can't see because page 335 of the book is not available for me on Google Books). Although at first glance, both words coming from Etruscan might seem to support the case for a relationship, I actually think that would make a connection harder to justify. As far as I know, the "s-mobile" phenomenon would not be expected to affect an Etruscan root, and I don't think word-initial partial reduplication is a known feature of the Etruscan language either.