I think that semantically the phrases are not idiomatic i.e. they do not have additional meaning assigned to the specific forms listed.
If you accept that then the meaning and the difference comes from the difference of "say" and "tell".
It should be noted that both words can mean exactly the same thing: "to communicate information" or can deal with specifics.
Tell
From etymology of the words the most obvious is that "to tell" comes from O.E. "to reckon, calculate, consider, account", with meanings:
- "to narrate, relate" from c.1000,
- "to make known by speech or writing, announce" from early 12c,
- "to reveal or disclose" from c.1400,
- "to order (someone to do something)" from 1590s,
In the sense evolution, cf. Fr. conter "to count," raconter "to recount;" It. contare, Sp. contar "to count, recount, narrate" (see more)
Def from dictionary, primary meaning:
Tell: Communicate information to someone in spoken or written words
Say
From O.E. secgan "to utter, say," which seem to had more stable meanings.
Def from dictionary, primary meaning:
Say: Utter words so as to convey information, an opinion, a feeling or intention, or an instruction
In context
Finally, putting it in context here is an attempt to outline the difference.
"Nothing to say" - of situation where the speaker want to express that there is nothing to be said; no appropriate words to reply or to respond to a situation.
John finished packing. There was nothing to say.
"Nothing to tell" - of situation where the speaker has nothing to narrate or recount.
John left. There is nothing to tell. (Lucy on the phone with a friend)
In the first example using "to tell" instead of "to say" would change the meaning; "to tell" implies a story (narrate, relate), announcement (make known by speech or writing) or disclosure (from reveal or disclose).
This is different and more specific compared to "to say" which literally means "to utter".
So, semantically they can both express the same thought, unless you use "to tell" to emphasize one of the more specific meanings, or if you use "to say" to express a meaning that is not matched there is a difference and they are not interchangeable (I tried to illustrate this in the example).
Here are a few examples to illustrate the difference between saying and telling in terms of semantics:
She said "Vogons!", but that did not tell me anything.
He told me to go away, but what he actually said was pretty vulgar.
Finally, here is an interesting ngram showing frequencies over time for additional pondering.