Yes
It's not a very technical or precise claim, but its essence is factually sound.
Using the common measure for "police brutality" as police killings,* a large majority of the cities with high police brutality have Democratic majors. While King did not qualify it further, this claim remains mostly true even when taking into account party prevalence among mayors.
As usual, do not mistake King's claim of correlation as causation. There might be an underlying factor yielding both results; changing party control wouldn't necessarily reduce policy brutality.
Also, there isn't any claim of statistical significance. Several dozen cities is a relatively small sample size.
Cities with high police killings
Earlier this year, security.org looked at cities with high police brutality: Which cities have the biggest problems with police brutality? (The source data comes from the aggregator Mapping Police Violence.)

(source: security.org)
(The criteria for a "major city" isn't given, but Scottsdale is 84th most populous in the U.S., with 262k people.)
Of the fifteen cities with the most police killings, 12 have Democratic mayors and 3 have Republican mayors.
- Laredo - D
- Orlando - D
- Las Vegas - D
- Tucson - D
- Scottsdate - R
- Mesa - R
- Albuquerque - D
- Phoenix - D
- Columbus - D
- Denver - D
- Louisville - D
- Aurora - R
- Atlanta - D
- St. Louis - D
- Kansas City - D
Cities with low police killings
While the above renders King's statement true, it's relevant context to understand how much of this is due simply to prevalence of Democratic mayors.
Of the fifteen cities with the least police killings, 8 have Democratic mayors and 6 have Republican mayors:
- New York - D
- Indianapolis - D
- El Paso - R
- District of Columbia - D
- Chicago - D
- San Jose - D
- Omaha - R
- Virginia Beach - R
- San Francisco - D
- Minneapolis - Other
- Wichita - R
- Seattle - D
- Nashville - D
- Corpus Christi - R
Mayor party prevalence
Of the top fifty U.S. cities, there are 35 Democrats and 13 Republicans. It would seem that large cities have mostly Democratic mayors, but not quite so many as to be proportionate to their presence in the earlier list.
* These numbers are for all police killings, whether officially ruled "justified" or not. This approach addresses a common concern about bias in judicial treatment.