My startup idea targets a rather specific target market:
My research is ongoing, but I would estimate that there are probably around 2000 - 3000 such companies recruiting at any one time.
Is this simply too small a target market? i.e. I'd probably need around 10% of it to use my service before I even made a 'reasonable living' from the startup (i.e. enough to give up my day job and look to build it further).
I'm wondering whether I should drop the idea in favour of something with a far broader appeal.
As a small company / start up I heartily recommend the niche. In general, it's often easier to market to a niche, particularly one you understand than a broad market. It lets you create a message that people can get their head around and understand how you fit. For example, SourceGear Vault's goal was to be "the most compelling replacement for Visual Source Safe". Consider if instead SourceGear said "to be the most compelling source code management system". They would have a really wide market - but it now tells me nothing about whether they're a product for me.
This is particularly important because if you are technically competent then marketing is likely going to be your biggest challenge - so anything you can do to make that task easier improves your odds of success. A focused niche makes it easier to pick where you invest your marketing expenses, how you reach that audience, and what are the key things you need to deliver to have a viable product.
That said, any strategy that requires you to get 10% of a market is likely a mistake unless you're sure you're in a "land grab" market - something about to break wide open or are incredibly well financed. That probably means you need to charge more or find another way to monetize your market so that you need a much smaller slice to be sustainable.
Startups need to focus. The more focus, the better. This focus allows you to serve your target market better than the competition. This does not mean that you don't think about scale or adjacent markets once you are successful. It does mean you start with something that is manageable and build from there.
It sounds like your application can be used by the whole world once you have established it. So, work on being the best in your niche and then expand from there. If you worry about scale and world domination right out the gate, you will become defocused and not be successful.
The way I think about this stuff is as a platform. What platform can I build that addresses a specific target market yet can cross-over to an adjacent market once I am successful. If you think of it that way, then you laser focus on your target market yet still have the ability to zig and zag or expand when the time is right.
Not only it is right to go after a niche, but you should also define your niche more precisely. "Small/medium businesses in the UK" is too much of a market. Go after a certain segment, like restaurant industry or anything with higher than average staff turnover rate.
I did try this: years ago we released software to serve "small/medium businesses worldwide" and we also released the same software but tailored to a very specific, extremely narrow niche. Needless to say the niche version sold better. BTW, we also were able to charge a premium for it compared to the general version.
There are lots of great books on go-to-market strategies for startups. One of my favorites is Crossing the Chasm, which, not coincidentally, also recommends your initial strategy should be to identify and dominate a niche market. Some others include Blue Ocean Strategy and 4 Steps to the Epiphany.