It is not clear what autocomplete function you are using in JS, if it is from a library or custom, but I’m assuming that it expects an array where locations is passed and not a string, which is what you’re feeding it.
The function you should be using is get_terms(), not wp_list_categories(), the former being used for returning an array of terms in a taxonomy, the latter is for returning a string of HTML markup. You can use the fields argument to filter which fields you want included in the results.
Example:
$locations = get_terms( array(
'taxonomy' => 'category',
'hide_empty' => false,
'fields' => 'names'
) );
Secondly, as mentioned above, your locations variable is populated with a string in JS not an array. This might be fine if the autocomplete function were to parse it as JSON automatically, but in that case your string would not be valid JSON anyway as you are outputting a <ul> markup string inside the brackets. Try this:
var locations = ["<?php echo implode('", "', $locations); ?>"];