Instead of using wp_list_categories, perhaps you could add some code to your first attempt and divide your $categories array into two arrays, then output each array in its own column:
We use cookies to offer you a better browsing experience, analyze site traffic and personalize content. Read about how we use cookies and how you can control them in our Cookie Policy. If you continue to use this site, you consent to our use of cookies.