Should we incorporate as German UG or UK Ltd?

The short, quick and general answer (that cannot replace specific legal advice) is:
Since you are based in Germany, it will – especially in view of the Brext - be easier and probably cheaper to set up and maintain a German company such as UG or, preferably, GmbH in Gemany.

For consistency, I refer to my two recent answers:

1. What is the difference between GmbH, UG, LTD ... https://secure.ipnexus.com/en/advice/questions/856
Germany introduced the Gesellschaft mit beschraenkter Haftung (GmbH, private limited liability company) over 120 years ago as capital company. According to the Law (Gesetz betreffend die Gesellschaften mit beschraenkter Haftung, GmbHG), 25000 EUR are required as minimum capital. For the GmbH this capital may partially or fully consist of non-cash capital, e.g. equipment, car, real estate.
In response to the UK Limited Company (Ltd), also usable in Germany under free movement in the European Union (EU), the Unternehmergesellschaft (haftungsbeschraenkt) (UG, private limited liability entrepreneurial company) was introduced in 2008 as a more attractive alternative for business starters.
Basically, the UG is a GmbH requiring only 1 EUR Minimum (cash) capital. However, UGs typically have about 10000 EUR.
Thus, a UG is easier / cheaper to start than a GmbH.
The UG has been widely accepted and replaced the UK Ltd.
For these reasons, the UG is presently very popular and trendy.
However, the conventional GmbH has a better Standing - which counts a lot!
Thus, if the founder(s) can provide the (cash or non-cash) capital, the GmbH is preferable over the UG.
By the way, for a quick start, it may be advisable to buy a shelf company (Mantelgesellschaft, for example Vorratsgesellschaft).
Further information:
DE Gesellschaft mit beschraenkter Haftung (GmbH, private limited liability company) https://de.wikipedia.org/wiki/Gesellschaft_mit_beschr%C3%A4nkter_Haftung_(Deutschland)
DE Unternehmergesellschaft (haftungsbeschraenkt) (UG, private limited liability entrepreneurial company) https://de.wikipedia.org/wiki/Unternehmergesellschaft_(haftungsbeschr%C3%A4nkt)
UK Limited Company (Ltd) https://de.wikipedia.org/wiki/Kapitalgesellschaft_(Vereinigtes_K%C3%B6nigreich)

2. Should we relocate from London to Berlin? https://secure.ipnexus.com/en/advice/questions/869
You recently - with the EU referendum clearly ahead - decided to establish your company in London, certainly you had your good reasons.
One week after the Brexit, everybody has an opinion and already offers his/her advice, albeit the road ahead is not clear; it is on unchartered territory.
Apparently, the EU referendum is not even legally binding, as the Parliament is sovereign.
While your concerns are understandable, for the time being:
Keep Calm and Carry On!