We search for lepton-flavor-violating tau decays into three leptons (electron or muon) using 535 fb-1 of data collected with the Belle detector at the KEKB asymmetric-energy e+e- collider. No evidence for these decays is observed, and we set 90% confidence level upper limits on the branching fractions of (2.0-4.1)x10^-8. These results improve upon our previously published upper limits by factors of 4.9 to 10.