This paper presents a new physical random access channel (PRACH) preamble design suitable for the next-generation 6G cellular communication systems operating in the sub-Terahertz (THz) bands. In these extremely high frequency channels, the subcarrier spacing (SCS) of the orthogonal frequency-division multiplexing (OFDM) based waveform should be significantly increased at least to MHz-level to mitigate the severe effect of phase noise, thus resulting in the OFDM symbol length of several hundreds of nano-seconds. Under this setup with nano-scale OFDM symbol length, a new paradigm of PRACH preamble design is required, since the conventional 5G PRACH only works under the assumption of sufficiently large OFDM symbol length to enable the base station (BS) to estimate the round-trip propagation delay (RTD) of users' non-synchronized uplink signals in a cell. To this end, we propose a new structure of two-part PRACH preamble and the corresponding two-step detection method. It is shown that the scalable structure of the proposed preamble design facilitates practical estimation of RTD at the BS under various sub-THz environments with very small OFDM symbol length as well as arbitrary cell size. The proposed schemes will provide important insights in designing sub-THz cellular systems adopting MHz-level SCS.