How long do you have to wait once you submit the paperwork?

The quick TL;DR answer: from the confirmed experiences of people who've applied during the decade — less than a year, and taking less than half a year is not unheard of. For me, it took four (4) months, but your mileage may vary. It seems that the average for most people over the last five years has been around six (6) to nine (9) months.

There are two phases to the application process: the time it takes to gather and get feedback for all the paperwork you need to submit, and the time from the formal submission to seeing a notification in the Official Gazette (官報 {kampō}) regarding your naturalization and getting a call back from your case worker telling you to come to the local 法務局 {hōmukyoku} (legal affairs bureau) to receive your 帰化者身分証明書 {kikasha mibun shōmeisho} (proof of identity of naturalized person) — which is a one-time use breeder document used to create your family register (戸籍 {koseki}) and other official Japanese-citizen documents at the city hall (市役所 {shiyakusho}) or the local ward office (区役所 {kuyakusho}).

Most everyone agrees that the majority of the time taken for the process is time spent on your side. That is, in between case officer appointments you will be given assignments to collect paperwork. Sometimes this is official paperwork for things that can only be retrieved overseas. And depending on the country, sometimes it can be difficult to retrieve this paperwork while living in Japan due to the need to show proof of identity in person or find out in person where that paperwork is collected. The paperwork most people complain about being the most difficult to obtain is vital records (birth certificates, marriage certificates, divorce certificates, death certificates).

Because this paperwork takes a long time to collect, and there is no time limit between case worker appointments or deadlines* regarding the collection of these documents, I've heard of some people taking years to gather the paperwork. However, the time this takes to do this is not a function of Japan's bureaucracy; it is a function of how fast you move, and how fast the foreign governments that provide vital records can move and how strict they are. None of the domestic paperwork (tax records, etc) that needs to be collected takes more than a couple days to collect; almost all of the paperwork can be done in the same business day from the time of the request.

* Some of the paperwork for things that change (tax records, for example) is required to be "fresh" for submission, being defined as certified current for three or six months or less. So if you wait too long between appointments to submit some paperwork, it's possible that you will be required to get transcripts that are more current to today's date.

The case worker's job is to make sure that your entire packet is in order and nothing is missing and the odds of approval are high once submitted. If an incomplete or poorly prepared packet is submitted to the 法務省 {hōmushō} (Ministry of Legal Affairs) and wastes their time, it reflects poorly on that case worker and the bureau that submitted it, after all.

So, once the paperwork is submitted, it is usually a matter of waiting. You may get a phone call or letter during this time regarding a minor detail that's missing (for example, I was asked to correct my desired 本籍 {honseki} (registered domicile) address from 〜５丁目１７番地 {~5 chōme 17 banchi} (~ district 5, land-plot 17) to 〜５丁目１７番 {5 chōme 17 ban} (~ district 5, block 17). They warn you that they do need a way to timely reach you via mail or telephone (sorry, no email) during the waiting time, and you do need to tell them when you leave or enter Japan. Being unreachable during the waiting process can cause your application to be rejected if there's a problem.

It's also possible, though unlikely, that your case worker may ask for one piece or two pieces of supplemental paperwork (for example, a college degree) that may be submitted via a provided envelope addressed to the bureau, which is to be mailed after the formal submission. Failure to mail this info in a timely manner or at all may delay your application or cause it to be rejected.

You will find out if you're accepted by reading about it first in the Official Gazette (官報 {kampō}) if you check it frequently from the internet or library — as they're required by law to publish the acceptance there first — followed by a phone call from your case worker or legal affairs bureau (法務局 {hōmukyoku}), followed by a notification in the postal mail.