I guess you are free to define your UUID for your service, you don't need to follow the format you mentioned. If you use 16bit UUID, it will be extended to BLE base uuid. See below question:
What range of Bluetooth UUIDs can be used for vendor defined profiles?
For reference, you can see inside bluez's source tree, plugins/gatt-example.c. For weight service, they are using arbitrary 128-bit UUID. See register_weight_service():
https://github.com/aguedes/bluez/blob/master/plugins/gatt-example.c
Here is the service on the run, connected with gatttool (bluez tool):
attr handle: 0x003c, end grp handle: 0x0040 uuid: 00001806-0000-1000-8000-00805f9b34fb
attr handle: 0x0041, end grp handle: 0x0049 uuid: 0000180e-0000-1000-8000-00805f9b34fb
attr handle: 0x004a, end grp handle: 0x0056 uuid: 00001811-0000-1000-8000-00805f9b34fb
attr handle: 0x0057, end grp handle: 0x005b uuid: 0000a0f0-0000-1000-8000-00805f9b34fb
attr handle: 0xfffa, end grp handle: 0xfffe uuid: feee74dc-a8de-3196-1149-d43596c00a4f
And the characteristics starting from handle 0xfffa:
handle: 0xfffa, uuid: 2800
handle: 0xfffb, uuid: 2802
handle: 0xfffc, uuid: 2803
handle: 0xfffd, uuid: e9258c1e-8962-c4b6-0b45-2c9018f28880
handle: 0xfffe, uuid: 2904
handle: 0xffff, uuid: 2901