Yes JSitemap can work fine with sh404sef.
The generation and routing of links is not managed directly by JSitemap, but is demanded to the SEF extension installed and enabled on your site, either native Joomla SEF or a third party solution such as sh404sef.
If you experiment issues about XML documents such as sitemaps being rendered as HTML, ensure that the setting '301 redirects from non-SEF to SEF' in the configuration of sh404sef is not enabled. If you still experiment issues after changing this setting you can also change the sh404sef configuration by component and choose 'Leave as non-sef' or 'Use Joomla router' for JSitemap.
Additionally it's important to ensure that the following parameter is disabled and set to 'No' as by default in order to always use native raw links for each sitemap:
As a plus that could be useful in certain cases, in the download area it's available a data source of type 'plugin' to integrate sh404sef URLs directly. This plugin fetches all URLs from the sh404sef database and use them to build the sitemap.