Ok, here are the benchmark results here with a 1-byte separator:

  10 x 10       0.244 usec   0.202 usec   +21%
 100 x 10       0.325 usec   0.326 usec    -0%
1000 x 10       0.691 usec   0.689 usec    +0%
  10 x 1000      18.2 usec    14.2 usec   +28%
 100 x 1000      39.8 usec    40.6 usec    -2%
1000 x 1000      94.6 usec      96 usec    -1%

and with an empty separator:

  10 x 10       0.245 usec   0.198 usec   +24%
 100 x 10       0.335 usec   0.286 usec   +17%
1000 x 10       0.637 usec   0.593 usec    +7%
  10 x 1000      18.9 usec    14.1 usec   +34%
 100 x 1000      40.3 usec    36.2 usec   +11%
1000 x 1000      93.7 usec    96.9 usec    -3%

(Core i5 2500K, 64-bit, gcc)

I would say the empty separator case is interesting, because a common use case for bytes.join() is indeed fast concatenation. However, the 1-byte separator case could be dropped, which would simplify the patch and the heuristic.