Longest, thinnest trace length to decoupling capacitor before capacitor is effectively useless
The answer is unhelpfully "as short as possible", and/or "it depends".

Whether it needs to be 1mm, 1cm, or even 1m will depend on factors such as switching frequency, signalling standards, whether sensitive analogue components are involved, how much EMI you can get away with etc.

The purpose of the capacitor is to provide a nice low impedance path between supply rails. The longer and thinner the trace, the larger the inductance of said trace, and the higher the resulting impedance (remember inductors are short at DC, and increase in impedance with frequency).

If you have a signal that toggles very slowly, and/or can cope with noise generated on the signal due to poor decoupling, then you can get away with longer narrower traces. 

If however you have a signal running at hundreds of MHz, or into the GHz range, even a few millimetres of trace might be too high of an inductance. At this point even a via might add a lot of unwanted inductance.

In circuits with analogue electronics, things also get critical because supply noise and ground noise have a nasty habit of finding their way into analogue front ends.

The simplest way to find out is to build a prototype, and test it. If things work as expected and performance is within parameters, then your traces are short enough. If you find issues with noise or signal problems, poor decoupling may be a culprit.