It is possible that AssociateTo behaves in a way similar to AppendTo. If that is true then for each new key->value that you add to your association makes a new copy of the the existing key->value pairs and then inserts or updates one new key. That may mean it takes approximately c*34122^2 time to complete this.

An alternative might be to create a single list of all key->value pairs in a list and then do Association@list. If that will work then the result might take approximately c*34122 to complete.

Another possible optimization might be, because you seem to only be interested in the absolute value of the difference of two permutations, to only associate i,j for i less than or equal to j. That may eliminate approximately half your key->value pairs and you would modify your code to reverse i and j if i were greater than j when you want to look up an association.

Another probably much smaller optimization might be

Do[
  diff=Total@Abs[base[[i]]-base[[j]]]
  If[diff=0 || dif==2 || diff=4,
  ....

That seems to reduce by about 2/3 the number of value extractions from lists of 34122 items. That may or may not make any significant difference.

You could perhaps use the Outer function to compare all permutations with all permutations, but it looks like you want to associate an index with each permutation and that takes a little more knowledge to accomplish that when using Outer.

The Combinatorica package was available with earlier versions of Mathematica. You might see if it is included in your version. That included a NextPermutation function which would generate each subsequent permutation, one at a time, instead of creating all the permutations at once. If that works then you might trade longer execution time for less memory usage.

If you got NextPermutation working then you could generate and test each permutation and only save those which satisfied your conditions. I once found the source to the Combinatorica package on the net and was able to extract that single function for a problem I was working on. If you try this then please test it very carefully to make certain that it is correct for your problem.

Different idea, do not know whether this will help or not, probably not as much. Is

5 <= Total@#[[11 ;; 15]] <= 5

equivalent to

Total@#[[11 ;; 15]]==5

or perhaps even

#[[11 ;; 15]]=={1,1,1,1,1}

Another idea. Could you generate the permutations not including those 5 1's in columns 11-15 which might make for fewer permutations to generate and test. Perhaps something like

base = Select[Permutations[{0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0}],5<=Total@#[[1 ;; 10]]<=7&]

and adjust your code to understand that columns 11-15 are not present or you insert those 5 1's into the middle of each permutation after you generate it if needed.