So currently TimelessTemplate::getCatList() looks like this:

	protected function getCatList( $list, $id, $message ) {
		$html = '';

		$categories = [];
		// Generate portlet content
		foreach ( $list as $category ) {
			$title = Title::makeTitleSafe( NS_CATEGORY, $category );
			if ( !$title ) {
				continue;
			}
			$categories[ htmlspecialchars( $category ) ] = [ 'links' => [ 0 => [
				'href' => $title->getLinkURL(),
				'text' => $title->getText()
			] ] ];
		}

		$html .= $this->getPortlet( $id, $categories, $message );

		return $html;
	}

For each category link, it only knows of two parameters: href and text (link target and displayed text, respectively).

Making red category links, well, red, appears seemingly easy enough:

	protected function getCatList( $list, $id, $message ) {
		$html = '';

		$categories = [];
		// Generate portlet content
		foreach ( $list as $category ) {
			$title = Title::makeTitleSafe( NS_CATEGORY, $category );
			if ( !$title ) {
				continue;
			}
			$portletContent = [
				'href' => $title->getLinkURL(),
				'text' => $title->getText()
			];
			// Give nonexistent things this class so that they can be styled
			// as red (or some other color) to distinguish them from categories
			// that actually exist
			// @see https://phabricator.wikimedia.org/T175713
			if ( !$title->exists() ) {
				$portletContent['class'] = 'new';
				$portletContent['href'] = $title->getLinkURL( [ 'action' => 'edit', 'redlink' => 1 ] );
			}
			$categories[htmlspecialchars( $category )] = [ 'links' => [ 0 => $portletContent ] ];
		}

		$html .= $this->getPortlet( $id, $categories, $message );

		return $html;
	}

But this does not take the link's (the <a> element) title parameter into account at all -- currently (in non-Timeless skins) when you hover your mouse over a red link, the contents of [[MediaWiki:Red-link-title]] are shown, e.g. if our nonexistent category is named "FooBar test", hovering over the category link would show "Category:FooBar test (page does not exist)" if the category would not exist, and just plain "Category:FooBar test" if the Category: page would exist.
The proper solution would be to use LinkRenderer, like this: MediaWiki\MediaWikiServices::getInstance()->getLinkRenderer()->makeLink( $title, $title->getText() ) ...except that Timeless cannot handle that as it expects that TimelessTemplate::getPortlet() is passed an array as the 2nd parameter.

cc'ing @Legoktm for further input.

How do Vector/MonoBook handle this properly?

In T175713#3613117, @ashley wrote:

The proper solution would be to use LinkRenderer, like this: MediaWiki\MediaWikiServices::getInstance()->getLinkRenderer()->makeLink( $title, $title->getText() ) ...except that Timeless cannot handle that as it expects that TimelessTemplate::getPortlet() is passed an array as the 2nd parameter.

I think adding a function to LinkRenderer that outputs the link in makeListItem (or whatever) format seems reasonable.

Hi, I allow myself to ping, it seems to me one of the most problematic bugs of the skin.

Change 442021 had a related patch set uploaded (by Evad37; owner: Evad37):
[mediawiki/skins/Timeless@master] Fix display of categories in the sidebar

https://gerrit.wikimedia.org/r/442021

Change 442021 merged by jenkins-bot:
[mediawiki/skins/Timeless@master] Fix display of categories in the sidebar

https://gerrit.wikimedia.org/r/442021