I think the misunderstanding is with how Merge works, which is (with my bolding and italicizing), that it:
Combines multiple input datasets of the same data type into a single,
new output dataset.
Let's assume that your loc_list is
["A","B"], then the first time Merge runs in your script the syntax used evaluates to:
arcpy.Merge_management(["AOI_test.shp", "AOI_A.shp"], "AOI_test.shp")
Your output dataset is NOT new, it is the same as one of your two inputs.
In response to our discussion as comments I have included the untested code below to illustrate how I am suggesting that you could perform a single Merge. As far as I can see there is no documented limit to the number of feature classes that can be merged together, but it will be interesting to see if 600 is too many. I would first test with 3 feature classes to make sure the code works first then see if any limitation is encountered when you retest with all 600*.
AOI_test = "AOI_test.shp"
arcpy.env.overwriteOutput = True
aoiList = 
for i in loc_list:
AOI = "AOI_" + i + ".shp"
arcpy.Select_analysis("locality", AOI, " \"LOCALITY\" = '%s'" % (i))