Interesting question. We do know the letter was chosen by Clausius in 1850(1), as was the letter S for entropy in 1862(2). I did a little sleuthing and it appears that nobody know why S and U were chosen. I couldn't find anything for U but found some speculation that S was chosen to honor Sadi Carnot. However most speculation seems to be that it was an arbitrary choice.
Thus I think a better explanation is found by noticing that many of the earlier thermodynamic variable representations fall together: Q (heat), R (gas constant) T (temperature). "R" for the gas constant has been used since at least 1834 (by Clapeyron). Stands to reason that S and U being in such close proximity to Q R and T cannot be mere coincidence. (Especially S, being related to the quantity Q/T).
It is notable that U and S are not the only symbols that have been used throughout history, particularly early on, but they are certainly the symbols that stuck.
1. Clausius, Rudolf. (1850). "On the Motive Power of Heat, and on the Laws Which can be Deduced From it for the Theory of Heat." Poggendorff's Annalen der Physik, LXXIX, 368, 500.
2. Clausius, Rudolf. (1862). "On the Application of the Theorem of the Equivalence of Transformations to Interior Work", (pp. 215-250). Communicated to the Naturforschende Gesellschaft of Zurich, Jan. 27th, 1862; published in the Viertaljahrschrift of this Society, vol. vii. P. 48; in Poggendorff’s Annalen, May 1862, vol. cxvi. p. 73; in the Philosophical Magazine, S. 4. vol. xxiv. pp. 81, 201; and in the Journal des Mathematiques of Paris, S. 2. vol. vii. P. 209.